How should I practice Intersect Two Interval Lists?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Superhuman phone screen problems in FastPrep.

Is Intersect Two Interval Lists associated with Superhuman?

FastPrep tags this as a Superhuman phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Intersect Two Interval Lists

Learn this problem

● Medium

SuperhumanFULLTIMEPHONE SCREEN

Problem statement

You are given two lists of closed integer intervals, firstList and secondList. Within each list, intervals are sorted by start value and are pairwise disjoint.

Return every nonempty intersection between an interval in firstList and an interval in secondList, ordered by increasing position.

For two closed intervals [a, b] and [c, d], their intersection is nonempty when max(a, c) <= min(b, d), including intersections consisting of one endpoint.

Function

intervalIntersections(firstList: int[][], secondList: int[][]) → int[][]

Examples

Example 1

firstList = [[0,2],[5,10],[13,23],[24,25]]secondList = [[1,5],[8,12],[15,24],[25,26]]return = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Each output interval is the overlap of the current pair. Endpoint-only overlaps such as [5,5] are included because the intervals are closed.

Example 2

firstList = [[1,3],[5,9]]secondList = []return = []

There can be no intersections when one list is empty.

Example 3

firstList = [[-3,0],[4,7]]secondList = [[0,4],[8,10]]return = [[0,0],[4,4]]

The first two pairs touch at 0 and 4. The final intervals do not overlap.

Constraints

0 <= firstList.length, secondList.length <= 10^5.
Every interval has exactly two signed 32-bit integer endpoints [start, end] with start <= end.
Within each list, intervals are sorted by start and pairwise disjoint.
Return intersections in ascending order.
Your traversal should run in O(n + m) time apart from output storage.