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.

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].