Merge Two Lists of Non-Overlapping Intervals
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two lists of closed integer intervals, `a` and `b`. Each interval is represented as a pair `[start, end]` with `start <= end`, and it covers every integer point in the inclusive range `[start, end]`.
Within **each** list the intervals are already sorted in increasing order of `start` and are pairwise **non-overlapping** (no two intervals in the same list share any point). The two lists, however, may overlap with each other arbitrarily.
Merge both lists into a **single** list of non-overlapping closed intervals that covers exactly the union of all input intervals, sorted by `start`. Two intervals that overlap **or that touch at a shared endpoint** must be combined into one. For example, `[1, 3]` and `[3, 5]` combine into `[1, 5]` (they share the endpoint `3`), and `[1, 4]` and `[2, 6]` combine into `[1, 6]`. Intervals with a gap between them — such as `[1, 2]` and `[4, 5]` — stay separate (the value `3` is not covered, and the endpoints `2` and `4` are not equal).
### Examples
**Example 1**
```
Input: a = [[1, 3], [6, 9]], b = [[2, 5], [8, 10]]
Output: [[1, 5], [6, 10]]
```
Explanation: `[1, 3]` and `[2, 5]` overlap → `[1, 5]`. `[6, 9]` and `[8, 10]` overlap → `[6, 10]`.
**Example 2**
```
Input: a = [[1, 2], [5, 6]], b = [[3, 4]]
Output: [[1, 2], [3, 4], [5, 6]]
```
Explanation: `[1, 2]` and `[3, 4]` neither overlap nor share an endpoint (they leave a gap), so all three intervals stay separate.
**Example 3**
```
Input: a = [], b = [[1, 5]]
Output: [[1, 5]]
```
### Constraints
- `0 <= a.length, b.length`
- `1 <= a.length + b.length <= 100000`
- For every interval, `start <= end`, and both fit in a signed 32-bit integer.
- Each input list is sorted by `start` and internally non-overlapping.
### Output
Return the merged list of non-overlapping closed intervals, sorted by `start`.
Quick Answer: This question evaluates a candidate's ability to merge two pre-sorted, non-overlapping interval lists into a single consolidated set, a core array and two-pointer/merging skill in coding interviews. It tests correct handling of edge cases like touching endpoints versus true gaps, assessing precision in interval logic and algorithmic reasoning under linear-time constraints.
You are given two lists of closed integer intervals, `a` and `b`. Each interval `[start, end]` (with `start <= end`) covers every integer in the inclusive range `[start, end]`.
Within **each** list the intervals are already sorted by `start` and are pairwise **non-overlapping**. The two lists may overlap with each other arbitrarily.
Merge both lists into a **single** list of non-overlapping closed intervals covering exactly the union of all inputs, sorted by `start`. Two intervals that overlap **or touch at a shared endpoint** must be combined: `[1, 3]` and `[3, 5]` become `[1, 5]`; `[1, 4]` and `[2, 6]` become `[1, 6]`. Intervals with a gap stay separate: `[1, 2]` and `[4, 5]` remain two intervals (the value `3` is uncovered and the endpoints `2` and `4` differ).
### Examples
**Example 1**
```
Input: a = [[1, 3], [6, 9]], b = [[2, 5], [8, 10]]
Output: [[1, 5], [6, 10]]
```
**Example 2**
```
Input: a = [[1, 2], [5, 6]], b = [[3, 4]]
Output: [[1, 2], [3, 4], [5, 6]]
```
**Example 3**
```
Input: a = [], b = [[1, 5]]
Output: [[1, 5]]
```
### Constraints
- `0 <= a.length, b.length` and `1 <= a.length + b.length <= 100000`.
- Every interval has `start <= end`, both fitting in a signed 32-bit integer.
- Each input list is sorted by `start` and internally non-overlapping.
Constraints
- 0 <= a.length, b.length; 1 <= a.length + b.length <= 100000
- For every interval, start <= end, both fit in a signed 32-bit integer
- Each input list is sorted by start and internally non-overlapping
- Combine intervals that overlap OR touch at a shared endpoint; leave gaps separate
Examples
Input: ([[1, 3], [6, 9]], [[2, 5], [8, 10]])
Expected Output: [[1, 5], [6, 10]]
Explanation: [1,3] & [2,5] overlap -> [1,5]; [6,9] & [8,10] overlap -> [6,10].
Input: ([[1, 2], [5, 6]], [[3, 4]])
Expected Output: [[1, 2], [3, 4], [5, 6]]
Explanation: [1,2], [3,4], [5,6] all leave gaps, so nothing merges.
Input: ([], [[1, 5]])
Expected Output: [[1, 5]]
Explanation: One list is empty; the other passes through unchanged.
Input: ([[1, 3]], [[3, 5]])
Expected Output: [[1, 5]]
Explanation: They share the endpoint 3, so closed intervals merge into [1,5].
Input: ([], [])
Expected Output: []
Explanation: No intervals at all yields an empty result.
Input: ([[-5, -1], [2, 4]], [[-3, 0]])
Expected Output: [[-5, 0], [2, 4]]
Explanation: [-5,-1] & [-3,0] overlap -> [-5,0]; [2,4] is separated by a gap.
Input: ([[1, 10]], [[2, 3], [4, 5]])
Expected Output: [[1, 10]]
Explanation: [2,3] and [4,5] are fully contained inside [1,10]; extending by max keeps [1,10].
Hints
- Because touching endpoints must merge (closed intervals), merge whenever the next interval's start is <= the current interval's end.
- You can concatenate both lists and sort by start in O(n log n), then do one linear sweep — or, since each list is already sorted, two-pointer merge them into sorted order first.
- During the sweep, extend the last interval's end to max(last_end, cur_end) instead of overwriting it, so a fully contained interval like [2,3] inside [1,10] doesn't shrink the result.