Compute the Union of Two Sorted Interval Lists
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Union of Two Sorted Interval Lists
## Problem
You are given two lists of closed integer intervals. Within each list, intervals are sorted by start value and do not overlap. Compute their union as one list of closed intervals, sorted by start value and containing no overlaps.
Intervals that share an endpoint overlap because the intervals are closed.
### Function Contract
Implement `unionIntervals(first, second)`.
- Input: two sorted lists of two-element integer lists `[start, end]`.
- Output: the merged union as a new sorted list.
### Rules and Edge Cases
- Either input list may be empty.
- An interval from one list may overlap or contain intervals from the other list.
- Duplicate intervals are valid.
- The two input lists may have different lengths.
### Example
```text
Input:
first = [[1, 3], [7, 9]]
second = [[2, 6], [8, 10], [12, 13]]
Output: [[1, 6], [7, 10], [12, 13]]
```
```hint Preserve sorted order without resorting
At each step, compare the next unconsumed interval from each list and take the one with the smaller start.
```
```hint Merge into one running result
Once the next interval is known, only the final interval already in the result can overlap it.
```
Quick Answer: Compute the union of two sorted, nonoverlapping lists of closed intervals. Merge the two streams in linear time, combining endpoint-touching, duplicate, contained, and cross-list intervals correctly.
Given two lists of closed integer intervals, each already sorted by start and internally nonoverlapping, return their sorted nonoverlapping union. Closed intervals that share an endpoint merge.
Constraints
- 0 <= first.length, second.length <= 1,000.
- Every interval has two integer endpoints start <= end in [-10^12, 10^12].
- Within each input list, intervals are sorted by start and do not overlap as closed intervals.
- The output must be sorted and must merge intervals that share an endpoint.
Examples
Input: ([], [])
Expected Output: []
Explanation: Two empty inputs have an empty union.
Input: ([[1, 3]], [])
Expected Output: [[1, 3]]
Explanation: One nonempty input is preserved.
Hints
- Select the next interval with the smaller start without sorting the combined inputs again.
- After that selection, only the final interval already emitted can overlap the next one.