Find Intersections Between Two Interval Lists
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find Intersections Between Two Interval Lists
Implement `interval_intersections(first, second)`.
`first` and `second` are lists of closed integer intervals `[start, end]`. Within each list, intervals are pairwise disjoint and sorted by start. Return every non-empty intersection between an interval in `first` and an interval in `second`, in ascending order.
Because intervals are closed, two intervals that meet at one endpoint intersect at that single point.
## Example
```text
first = [[0, 2], [5, 10], [13, 23], [24, 25]]
second = [[1, 5], [8, 12], [15, 24], [25, 26]]
```
Return:
```text
[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
```
## Constraints
- `0 <= len(first), len(second) <= 100_000`
- `-10**9 <= start <= end <= 10**9`
- Each input list is sorted and internally pairwise disjoint.
Quick Answer: Find every non-empty intersection between two sorted lists of disjoint closed intervals. Preserve ascending order and correctly include intersections where intervals meet at a single endpoint.
Implement interval_intersections(first, second). Each input is a start-sorted list of pairwise disjoint closed integer intervals [start, end]. Return every non-empty cross-list intersection in ascending order; touching endpoints form a one-point intersection.
Constraints
- 0 <= len(first), len(second) <= 100,000
- -10^9 <= start <= end <= 10^9
- Each list is sorted and internally disjoint.
Examples
Input: ([], [])
Expected Output: []
Explanation: Checks empty, touching, nested, and separated intervals.
Input: ([[0, 2]], [])
Expected Output: []
Explanation: Checks empty, touching, nested, and separated intervals.
Hints
- Compare one interval from each list at a time.
- After checking an overlap, advance the interval that ends first.