Interval Intersections
MediumTwo Pointers · LinkedIn
You are given two lists of closed intervals, first and second. Each interval is [start, end] with start <= end and includes both endpoints. Within each list, the intervals are sorted by start and do not overlap or touch each other.
Return the intersection of the two lists: every maximal range of points covered by an interval from first and an interval from second. Each piece is the overlap of one interval from each list, [max(starts), min(ends)].
- If two intervals share just one point (e.g.
[1, 4]and[4, 6]), that point is reported as[4, 4]. - Return the pieces sorted by start. Return an empty list if nothing overlaps (either list may be empty).
Example 1
- Input:
- first = [[0,4],[7,12],[15,20]], second = [[2,8],[10,16],[20,25]]
- Output:
- [[2,4],[7,8],[10,12],[15,16],[20,20]]
- Explanation
- Each overlap runs from the later start to the earlier end: [0,4] and [2,8] give [2,4], [7,12] and [2,8] give [7,8], and so on. [15,20] and [20,25] share only the point 20, reported as [20,20].
Example 2
- Input:
- first = [[0,5],[10,14]], second = [[3,11]]
- Output:
- [[3,5],[10,11]]
- Explanation
- The single interval [3,11] stretches across the gap between [0,5] and [10,14], so it overlaps both and produces two pieces.
Example 3
- Input:
- first = [[1,3]], second = [[4,6]]
- Output:
- []
- Explanation
- [1,3] ends before [4,6] starts. The intervals are closed, but 3 and 4 are still different points, so there is no overlap.
Constraints
0 <= first.length, second.length <= 10000 <= start <= end <= 10^9for every interval- Within each list,
endof one interval is less thanstartof the next