Interval List Intersections
Interval List Intersections: return intersections between two sorted lists of pairwise-disjoint closed intervals.
- 0 <= firstList.length, secondList.length <= 1000
- firstList.length + secondList.length >= 1
- 0 <= starti < endi <= 10⁹
- endi < starti+1
- 0 <= startj < endj <= 10⁹
- endj < startj+1
Intuition
Interval list intersections takes two lists of closed intervals — each list sorted and internally disjoint — and asks for every overlap between them. Comparing every interval against every other is O(n·m) and throws away both guarantees.
For a single pair of intervals, the overlap is settled by two values:
- The intersection runs from max(startA, startB) to min(endA, endB), and exists only when that start does not exceed that end.
Since these are closed intervals, start == end is a valid one-point intersection, so the test is <= rather than <. Using a strict comparison silently drops every touching pair.
The efficiency comes from deciding which pointer to advance. After comparing the current pair, look at which interval ends first. That interval cannot possibly overlap anything further along in the other list, because the other list is sorted and everything remaining there starts at or after the current interval — all of it lies beyond the earlier endpoint. So that interval is finished and its pointer moves on.
That turns the problem into a merge-style scan: each step either emits an intersection or discards an interval, and every interval is discarded exactly once. Two pointers, one pass, O(n + m).
When both intervals end at the same value, advancing either is safe — neither can overlap anything later — so no tie-breaking rule is needed.
Two sorted, internally disjoint interval lists invite a two-pointer merge. After processing a pair, the earlier-ending interval is permanently exhausted relative to all future intervals.
Approach
Before reading on: price up what the direct approach costs here, then ask what sorting by one endpoint makes obvious that was hidden before. Aim for O(m + n) time and O(1) excluding output space.
Compute the overlap of the current pair
The intersection spans max of the two starts to min of the two ends. These two expressions capture every case — full containment, partial overlap, and no overlap at all — without any branching on which interval starts first.
Emit only when start does not exceed end
Append the interval when start <= end. The equality matters: these are closed intervals, so a shared endpoint is a legitimate one-point intersection, and using < drops those results.
Advance the pointer that ends first
Move past whichever interval has the smaller end. Everything remaining in the other list starts at or after the current position, so that interval cannot overlap anything further along — it is finished.
Break ties either way
When both ends are equal, advancing either pointer is correct, since neither interval can overlap a later one from the opposite list. No tie-breaking rule is needed, which is worth noting since it looks like it should matter.
Rely on both input guarantees
Sortedness lets you discard an interval permanently; disjointness within each list means the current pair is the only possible overlap at this position. Without both, this scan would be incorrect, not merely slower.
Cost of the merge scan
Each step advances at least one pointer, so the scan is O(n + m) time with O(1) space beyond the output — compared with O(n·m) for comparing every pair.
Solution & live demo
Common pitfalls
Using union boundaries
start = min(a[0], b[0]) end = max(a[1], b[1])
start = max(a[0], b[0]) end = min(a[1], b[1])
Intersection keeps only points inside both intervals.
Dropping endpoint intersections
if start < end:
if start <= end:
Closed intervals intersect when one ends exactly where the other begins.
Advancing the later-ending interval
if a[1] < b[1]:
j += 1if a[1] < b[1]:
i += 1The earlier-ending interval cannot reach any later counterpart and is the one that must be discarded.
Edge cases
The loop never runs and returns an empty result.
The non-strict overlap check returns that endpoint as [x, x].
The contained interval is returned, then its pointer advances because it ends first.