Merge overlapping closed intervals into a sorted list of disjoint intervals
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of closed intervals with integer endpoints, in no particular order. Merge every group of intervals that overlap, and return the resulting intervals sorted by their start.
### Function Signature
```python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
```
`intervals[i] = [start, end]` is the closed interval from `start` to `end`, including both endpoints.
### Rules
- Two intervals overlap when they share at least one point. Intervals that only touch, such as `[1, 4]` and `[4, 5]`, overlap because both contain 4. Intervals such as `[1, 2]` and `[3, 4]` share no point and do not overlap.
- Merging is transitive: if A overlaps B and B overlaps C, all three become one interval, even when A and C do not overlap each other.
- A merged interval is `[smallest start, largest end]` over its group.
- The input may contain duplicate intervals and intervals contained in other intervals.
- Return the merged intervals sorted by start in ascending order. Merged intervals are pairwise disjoint, so this order is unique.
### Constraints
- `1 <= len(intervals) <= 10^4`
- `0 <= start <= end <= 10^9` for every interval
### Examples
**Example 1**
```text
Input: intervals = [[2, 5], [9, 12], [4, 7], [13, 15]]
Output: [[2, 7], [9, 12], [13, 15]]
```
`[2, 5]` and `[4, 7]` share the points 4 and 5, so they merge into `[2, 7]`. `[9, 12]` and `[13, 15]` share no point, so they stay separate.
**Example 2**
```text
Input: intervals = [[6, 8], [1, 6]]
Output: [[1, 8]]
```
The two intervals touch at 6, which counts as overlapping. The output is sorted by start even though the input was not.
**Example 3**
```text
Input: intervals = [[5, 7], [1, 2], [3, 4], [2, 3], [9, 9]]
Output: [[1, 4], [5, 7], [9, 9]]
```
`[1, 2]`, `[2, 3]` and `[3, 4]` chain together through the shared points 2 and 3. `[1, 4]` and `[5, 7]` share no point, so they stay separate, and `[9, 9]` is a single point.
Overview: Coding problem: given closed integer intervals in any order, merge every group of overlapping or touching intervals and return the disjoint result sorted by start. It tests interval reasoning, correct handling of shared endpoints, duplicates and nested intervals, and a well-defined output order.
You are given a list `intervals` of closed intervals with integer endpoints, in no particular order. `intervals[i] = [start, end]` is the closed interval from `start` to `end`, including both endpoints. Merge every group of intervals that overlap, and return the resulting intervals sorted by their start.
**Rules**
- Two intervals overlap when they share at least one point. Intervals that only touch, such as `[1, 4]` and `[4, 5]`, overlap because both contain 4. Intervals such as `[1, 2]` and `[3, 4]` share no point and do not overlap.
- Merging is transitive: if A overlaps B and B overlaps C, all three become one interval, even when A and C do not overlap each other.
- A merged interval is `[smallest start, largest end]` over its group.
- The input may contain duplicate intervals, intervals contained in other intervals, and single-point intervals (`start == end`).
- Return the merged intervals as a list of `[start, end]` pairs sorted by start in ascending order. Merged intervals are pairwise disjoint, so this order is unique.
**Constraints**
- `1 <= len(intervals) <= 10^4`
- `0 <= start <= end <= 10^9` for every interval
- Every input and output value fits in a signed 32-bit integer; no value exceeds 2^31 - 1.
**Example 1**
```text
Input: intervals = [[2, 5], [9, 12], [4, 7], [13, 15]]
Output: [[2, 7], [9, 12], [13, 15]]
```
`[2, 5]` and `[4, 7]` share the points 4 and 5, so they merge into `[2, 7]`. `[9, 12]` and `[13, 15]` share no point, so they stay separate.
**Example 2**
```text
Input: intervals = [[5, 7], [1, 2], [3, 4], [2, 3], [9, 9]]
Output: [[1, 4], [5, 7], [9, 9]]
```
`[1, 2]`, `[2, 3]` and `[3, 4]` chain together through the shared points 2 and 3. `[1, 4]` and `[5, 7]` share no point, so they stay separate, and `[9, 9]` is a single point.
Constraints
- 1 <= len(intervals) <= 10^4
- 0 <= start <= end <= 10^9 for every interval
- Every input and output value fits in a signed 32-bit integer; no value exceeds 2^31 - 1
Examples
Input: ([[2, 5], [9, 12], [4, 7], [13, 15]],)
Expected Output: [[2, 7], [9, 12], [13, 15]]
Explanation: Source example 1: [2, 5] and [4, 7] share 4 and 5 and merge; [9, 12] and [13, 15] share no point.
Input: ([[6, 8], [1, 6]],)
Expected Output: [[1, 8]]
Explanation: Source example 2: touching at 6 counts as overlap; output is sorted by start although the input was not.
Hints
- Touching counts: [1, 4] and [4, 5] share the point 4, so they overlap, while [1, 2] and [3, 4] share no point.
- Overlap is transitive: an interval can join a group through another member even if it does not overlap the first interval of that group.
- A merged interval runs from the smallest start to the largest end in its group, and an interval contained in another can end before the group does.