Interval List Intersections
You are given two lists of closed intervals; each list is sorted by start and contains pairwise disjoint intervals. Return the list of all intersections between an interval of the first list and one of the second.
- 0 ≤ len(A), len(B) ≤ 1000
- 0 ≤ start ≤ end ≤ 10^9
- Each list is sorted and disjoint
- Two sorted interval lists
- Overlap of
[a,b]and[c,d]is[max(a,c), min(b,d)]if non-empty - Advance whichever interval ends first — merge-style pointers
Sort by start (or end) time and sweep: two intervals overlap iff the next start is before the current end, and after sorting each interval only needs comparing with the one being built. Counting concurrent intervals is a sweep over sorted endpoints, or a min-heap of end times.
Walk both lists with an index each. At every step compute the candidate intersection [max(starts), min(ends)] and emit it if start ≤ end. Then advance the pointer of the interval with the smaller end, because that interval cannot intersect anything further in the other list. This is a merge of two sorted sequences and touches each interval once.
- Checking every pair is O(m · n); a sweep line over all 2(m+n) endpoints also works and generalizes to more than two lists.