Intersect Two Sorted Lists of Disjoint Intervals
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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]`.
Overview: Intersect two sorted lists of disjoint closed intervals in linear time, retaining one-point endpoint overlaps and advancing whichever current interval ends first.
Given two lists of closed intervals, return every pairwise intersection in sorted order. Within each input list, intervals are sorted by start and do not overlap. Each interval is [start, end] with start no greater than end, and touching closed endpoints form a one-point intersection.
Constraints
- Each input list contains at most 200000 intervals.
- Every interval is [start, end] with start <= end.
- Endpoint values lie in [-10^9, 10^9].
- Within each input list, intervals are sorted by start and do not overlap.
- Touching endpoints form a one-point intersection.
Examples
Input: ([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]])
Expected Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
Explanation: This is the source example and includes ordinary overlaps and touching endpoints.
Input: ([], [[1, 3]])
Expected Output: []
Explanation: If either list is empty, there are no intersections.
Hints
- The overlap of two closed intervals starts at the larger start and ends at the smaller end.
- After considering a pair, the interval that ends first cannot meet a later interval on the other side.