182. Overlapping Schedules
Two colleagues each send a list of availability windows. A window [x, y] means the person is free at every moment from min(x, y) to max(x, y), both ends included, and moments are real numbers, not only whole minutes. Windows inside one list may come in any order and may overlap or touch.
Return the stretches of time during which both colleagues are free, as an array of [start, end] pairs sorted in increasing order. Each stretch must be maximal: it may not overlap or touch another entry of the answer. A single shared moment is a valid stretch such as [4, 4]. If the two colleagues are never free together, return an empty array.
Example 1
- Input:
- a = [[1,3],[5,8],[10,12]], b = [[2,6],[11,15]]
- Output:
- [[2,3],[5,6],[11,12]]
- Explanation:
Both are free during 2 to 3, 5 to 6 and 11 to 12; the other parts of each list have no partner window.
Example 2
- Input:
- a = [[3,6],[1,3]], b = [[6,9],[1,0]]
- Output:
- [[1,1],[6,6]]
- Explanation:
The first list merges to the single stretch 1 to 6, because its windows share the moment 3. The second list is free during 0 to 1 and 6 to 9. They meet only at the single moments 1 and 6.
Example 3
- Input:
- a = [[1,2]], b = [[3,4]]
- Output:
- []
- Explanation:
The windows never overlap, so the answer is empty.
Constraints
0 ≤ a.length, b.length ≤ 105
a[i].length == b[i].length == 2
0 ≤ a[i][0], a[i][1], b[i][0], b[i][1] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 6,000 msC++ 1,500 msJava 3,000 msJavaScript 3,000 msTypeScript 3,000 ms
Expected complexity
- Time
- O(n log n + m log m)
- Space
- O(n + m)