Interval List Intersections
Medium · Intervals · Array · Two Pointers · Line Sweep
Problem
You are given two lists of closed intervals, firstList and secondList. Within each list the intervals are pairwise disjoint and sorted by start.
Return the intersection of the two lists: every closed interval of points that lies in some interval of firstList and in some interval of secondList, sorted by start.
Two closed intervals [a, b] and [c, d] intersect in [max(a, c), min(b, d)] when that range is not empty. It can be a single point, such as [9, 9].
Examples
Input: firstList = [[1,4],[6,9]], secondList = [[3,7],[9,12]] Output: [[3,4],[6,7],[9,9]]
[3,7] meets both intervals of the first list, and 9 is shared as a single point.
Input: firstList = [[0,2]], secondList = [[5,6]] Output: []
The lists never overlap.
Input: firstList = [[1,10]], secondList = [[2,3],[5,6]] Output: [[2,3],[5,6]]
Both small intervals lie inside [1,10].
Constraints
- 0 <= len(firstList), len(secondList) <= 1000
- len(firstList) + len(secondList) >= 1
- 0 <= start_i < end_i <= 10^9
- within each list, end_i < start_(i+1)
Approaches
- Check every pair of intervals — time O(n · m), space O(1) beyond the answer
Follow-up
What if the lists were not sorted, or the intervals within one list could overlap? Sort each list and merge its overlapping intervals first; then the same walk works. For k lists at once, keep one pointer per list: the overlap runs from the latest start to the earliest end, and the interval that ends first is the one to advance.
Related problems
Start free on Cariara · Coding problems · System design studio
