Interval List Intersections
Medium · intervals
Two colleagues each keep a list of the time slots when they are free. A slot [start, end] is a range of whole minutes, with both ends included. Within one list the slots are sorted by start, and no two slots share a minute.
Return every slot when both colleagues are free: for each slot of first_list and each slot of second_list, the minutes they have in common, written as one range. A single shared minute counts, so [1, 3] and [3, 5] share the range [3, 3].
Return the ranges sorted by start. If the two lists never overlap, return an empty list.
Examples
Example 1
Input: first_list = [[1, 4], [7, 9], [12, 12]], second_list = [[3, 8], [9, 15]]
Output: [[3, 4], [7, 8], [9, 9], [12, 12]]
[1, 4] and [3, 8] share 3 to 4. [7, 9] meets [3, 8] on 7 to 8 and [9, 15] on 9 alone. [12, 12] lies inside [9, 15].
Example 2
Input: first_list = [[2, 6]], second_list = [[7, 9]]
Output: []
The only two slots do not share a minute, so the answer is empty.
Example 3
Input: first_list = [[0, 10]], second_list = [[1, 2], [4, 4], [6, 8]]
Output: [[1, 2], [4, 4], [6, 8]]
The one long slot contains all three slots of the second list, so each comes back unchanged.
Constraints
- 0 <= len(first_list), len(second_list) <= 1000
- Each slot has exactly two numbers, start and end
- 0 <= start <= end <= 10^9
- Within each list the slots are sorted by start and no two of them share a minute