579/670

579. Interval List Intersections

Medium

Your function receives two lists of closed intervals, firstList and secondList. Each interval [start, end] includes both endpoints, and within each list the intervals are sorted by start and pairwise disjoint. Either list may be empty.

Return every region of the number line that belongs to an interval from both lists — the intersection of the two lists — as a list of closed intervals sorted by start. The intersection of two closed intervals is either empty or the single closed interval [max(starts), min(ends)]; note it can be a single point like [5, 5].

Because each input list is sorted and disjoint, the answer is unique.

Example 1 on the number linefirstList (top) and secondList (middle) each cover disjoint stretches of the line. The gold row is every stretch covered by both — including single-point touches like [5,5], [24,24], and [25,25].

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Explanation: [0,2] and [1,5] share [1,2]; [5,10] meets [1,5] only at the point 5 and overlaps [8,12] on [8,10]; [13,23] and [15,24] share [15,23]; [24,25] touches [15,24] at 24 and [25,26] at 25.

Example 2:

Input: firstList = [[1,4],[7,9]], secondList = [[2,3],[6,8],[9,10]]

Output: [[2,3],[7,8],[9,9]]

Explanation: [2,3] sits entirely inside [1,4]; [7,9] overlaps [6,8] on [7,8] and touches [9,10] at the single point 9.

Constraints:

0 ≤ firstList.length, secondList.length ≤ 1000
0 ≤ start ≤ end ≤ 10⁹
Within each list, intervals are sorted by start and do not overlap (end_i < start_{i+1})

Hints:

Two closed intervals [a, b] and [c, d] intersect exactly when max(a, c) <= min(b, d) — and that pair of values IS the intersection.

Both lists are already sorted, so you never need to compare every pair. Keep one pointer per list and ask: after recording the (possible) overlap of the two current intervals, which pointer is safe to move?

Advance the pointer whose interval ends first. Everything that interval could still intersect has already been considered, because the other list's later intervals start even further right.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

Expected output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]