DSA problem
Interval List Intersections
You are given two lists of closed intervals, firstList and secondList, where each list is pairwise disjoint and sorted by start time. Return the intersection of these two interval lists. A closed interval [a, b] (with a <= b) denotes the set of all real numbers x with a <= x <= b. The intersection of two closed intervals is either empty or itself a closed interval — for example, the intersection of [1, 3] and [2, 4] is [2, 3].
Because each list is sorted and internally disjoint, the natural approach is a synchronized two-pointer scan. Start with one pointer at the beginning of each list. The intersection of the current pair [a, b] and [c, d] is [max(a, c), min(b, d)], which is a valid (non-empty) interval whenever max(a, c) <= min(b, d).
After recording any intersection, you must advance exactly one pointer. The correct rule is to advance the pointer of the interval whose end is smaller, because that interval cannot possibly intersect any later interval of the other list (everything later is to the right of its end). This keeps the algorithm linear in m + n.
The complexity is O(m + n) time with O(1) auxiliary space beyond the output, where m and n are the lengths of the two input lists. The pattern generalizes immediately to other problems that need to merge information from two sorted lists of intervals.
Examples
firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]][[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]firstList = [[1,3],[5,9]], secondList = [][]firstList = [[1,7]], secondList = [[3,10]][[3,7]]Constraints
- 0 <= firstList.length, secondList.length <= 1000
- firstList.length + secondList.length >= 1
- 0 <= start_i < end_i <= 10^9
- end_i < start_(i+1)
- Both lists are pairwise disjoint and sorted in ascending order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.