Intersect Two Sorted Lists of Disjoint Intervals

Problem

Given two lists of closed intervals, return all pairwise intersections. Within each input list, intervals are sorted by start and do not overlap. Return intersections in sorted order.

Function Contract

Implement interval_intersections(first, second) -> list[list[int]].

Constraints

• Each list contains at most 200000 intervals.
• Every interval is [start, end] with start <= end.
• Endpoint values lie in [-10^9, 10^9].
• Touching endpoints form a one-point intersection.

Examples

• [[0,2],[5,10],[13,23],[24,25]] and [[1,5],[8,12],[15,24],[25,26]] return [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].
• If either list is empty, return an empty list.

Hint: Advance the interval that ends first

After recording any overlap, the interval with the smaller end cannot intersect a later interval on the other side.

Edge Cases

• One interval can intersect several intervals from the other list.
• Identical intervals return that interval once.
• Closed endpoints make [1,2] and [2,3] intersect at [2,2].

Intersect Two Sorted Lists of Disjoint Intervals

Hints

1. The overlap of two closed intervals starts at the larger start and ends at the smaller end.
2. After considering a pair, the interval that ends first cannot meet a later interval on the other side.

Approach

Keep one pointer in each sorted list. The current intervals overlap exactly when max of their starts is no greater than min of their ends; in that case, those two values form their closed intersection. Afterward, advance the interval with the smaller end, because it cannot intersect any later interval in the other list. If the ends are equal, advancing either side is sufficient for the same reason. Every reported overlap is therefore valid and sorted, and no possible overlap is skipped before one pointer reaches the end.

• Time complexity: O(n + m)
• Space complexity: O(k) for k returned intersections, with O(1) auxiliary space