Schedule Overlaps
MediumTwo Pointers
Problem
Two people share their free time as lists of closed intervals [start, end]. Each list is sorted by start and its intervals are pairwise disjoint.
Return every interval during which both are free, sorted by start. A shared single instant such as [4, 4] counts.
Example 1
- Input:
- a = [[0, 3], [6, 9], [12, 20]], b = [[2, 7], [8, 13]]
- Output:
- [[2, 3], [6, 7], [8, 9], [12, 13]]
Each output interval is where one of a's blocks overlaps one of b's blocks.
Example 2
- Input:
- a = [[1, 4]], b = [[4, 8]]
- Output:
- [[4, 4]]
They touch at the instant 4.
Example 3
- Input:
- a = [[1, 5]], b = []
- Output:
- []
Constraints
- 0 ≤ a.length, b.length ≤ 10^4
- 0 ≤ start ≤ end ≤ 10^9
- Within each list, intervals are sorted and disjoint (end of one < start of the next)
Hint
Show the first hint
Two closed intervals overlap on [max(starts), min(ends)] when that range is non-empty.
Walkthrough
How to approach it
01Clarify before coding
- Are intervals closed? Yes, so touching endpoints produce a one-instant overlap.
- Are the inputs already sorted and disjoint within each list? Yes.
- Can either list be empty? Yes: the answer is empty.
02Brute force
Compare every interval of a with every interval of b and collect non-empty intersections, then sort them.
Cost: O(n · m) comparisons: 10^8 for 10^4 intervals each.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.