Interval list intersections of two sorted lists

You get two lists of closed intervals. Each list is sorted and its intervals don't overlap one another. Return every non-empty intersection between an interval of the first list and an interval of the second, in ascending order.

Interface

Unless you agree on a different interface with the interviewer, assume:

• interval_intersections(a: list[list[int]], b: list[list[int]]) -> list[list[int]]
• Intervals are closed, [start, end] with start <= end, so two intervals that touch at one point intersect in that point.

Example

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 24], [25, 26]]
interval_intersections(a, b)  ->  [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

interval_intersections([[1, 3]], [[3, 4]])  ->  [[3, 3]]
interval_intersections([[1, 2]], [])        ->  []

Constraints

• 0 <= len(a), len(b) <= 10^5
• Values are integers in [0, 10^9].

Clarifying questions

• Are intervals closed or half-open? Do touching intervals intersect?
• Are both lists sorted and internally non-overlapping?
• Can a list be empty?

What a strong answer covers

• Two pointers: the intersection of the current pair is [max(starts), min(ends)] when non-empty; then advance the pointer whose interval ends first.
• Why advancing the earlier-ending interval can't skip an intersection.
• O(len(a) + len(b)) time; output in ascending order without sorting.
• Edge cases: empty lists, single-point intersections, one interval covering many from the other list.
• Tests with the examples.

Follow-ups

• Intervals are half-open [start, end). What changes?
• Intersect k lists at once.
• The lists are streams too large for memory. Produce intersections as they arrive.