Overlap of Two Schedules

Medium

Two people's free time is given as lists of intervals mine and theirs. Each interval [start, end] is closed, meaning it includes both ends. Within each list the intervals do not overlap or touch, and they are sorted in increasing order. Find every stretch of time when both are free, that is, the intersections of intervals from mine with intervals from theirs. Return them in increasing order. An intersection may be a single point, such as [5, 5].

Example 1

mine=[[9, 12], [14, 17]], theirs=[[10, 15], [17, 19]] → [[10, 12], [14, 15], [17, 17]]

[9, 12] and [10, 15] give [10, 12]; [14, 17] and [10, 15] give [14, 15]; [14, 17] and [17, 19] touch at a single point, giving [17, 17].

Example 2

mine=[[0, 3]], theirs=[[5, 8]] → []

The intervals do not meet, so there is no common time.

Example 3

mine=[[2, 20]], theirs=[[3, 4], [6, 6], [18, 25]] → [[3, 4], [6, 6], [18, 20]]

Constraints

0 ≤ len(mine), len(theirs) ≤ 10⁴
0 ≤ start ≤ end ≤ 10⁹
Within each list, an interval ends strictly before the next one starts

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Line Sweep

Similar problems

Two Boards Holding Water Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Next Arrangement in Order Medium

Input

mine=[[9, 12], [14, 17]], theirs=[[10, 15], [17, 19]]

Expected

[[10, 12], [14, 15], [17, 17]]

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.