Combine Overlapping Closed Intervals Into a Sorted Disjoint List
Company: Lime
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a list of closed intervals with integer endpoints, in no particular order. Combine every group of overlapping intervals into a single interval, and return the resulting intervals sorted by their start.
### Function Signature
```python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
```
### Rules
- Each interval is `[start, end]` with `start <= end`, and it includes both endpoints.
- Two intervals overlap when they share at least one point. Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 5]`, overlap and must be combined. Intervals separated by a gap, such as `[1, 2]` and `[3, 4]`, do not overlap, even though no integer lies strictly between them.
- Overlap chains: if `A` overlaps `B` and `B` overlaps `C`, then `A`, `B` and `C` all end up in one interval, even when `A` and `C` do not overlap each other.
- Each returned interval is `[smallest start, largest end]` over the input intervals in its group, so the returned intervals cover exactly the same points as the input.
- The input may contain duplicates and intervals nested inside others.
- Return the combined intervals in ascending order of `start`. No two returned intervals overlap, so this order is unique.
### Constraints
- `1 <= len(intervals) <= 10^5`
- Every interval has exactly two integers, and `-10^9 <= start <= end <= 10^9`.
### Examples
**Example 1**
```text
Input: intervals = [[5, 7], [1, 4], [2, 3], [6, 9]]
Output: [[1, 4], [5, 9]]
```
`[2, 3]` lies inside `[1, 4]`. `[5, 7]` and `[6, 9]` overlap and combine into `[5, 9]`. `[1, 4]` and `[5, 9]` share no point.
**Example 2**
```text
Input: intervals = [[3, 4], [1, 2], [4, 4]]
Output: [[1, 2], [3, 4]]
```
`[3, 4]` and `[4, 4]` share the point 4, so they combine into `[3, 4]`. `[1, 2]` and `[3, 4]` share no point, so they stay separate.
**Example 3**
```text
Input: intervals = [[-5, -1], [-3, 2], [-5, -1]]
Output: [[-5, 2]]
```
The duplicate `[-5, -1]` and the overlapping `[-3, 2]` all combine into one interval.
Overview: Given an unordered list of closed integer intervals, possibly with duplicates, nested intervals and touching endpoints, combine every chain of overlapping intervals and return the disjoint result ordered by start. It tests interval reasoning, precise overlap rules at shared endpoints, and careful handling of edge cases.
You are given a list `intervals` of closed intervals with integer endpoints, in no particular order. Combine every group of overlapping intervals into a single interval, and return the resulting intervals sorted by their start.
Implement `merge_intervals(intervals)`, which returns the combined intervals as a list of `[start, end]` pairs.
### Rules
- Each interval is `[start, end]` with `start <= end`, and it includes both endpoints. A zero-length interval such as `[4, 4]` is the single point 4.
- Two intervals overlap when they share at least one point. Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 5]`, overlap and must be combined. Intervals separated by a gap, such as `[1, 2]` and `[3, 4]`, do not overlap, even though no integer lies strictly between them.
- Overlap chains: if `A` overlaps `B` and `B` overlaps `C`, then `A`, `B` and `C` all end up in one interval, even when `A` and `C` do not overlap each other.
- Each returned interval is `[smallest start, largest end]` over the input intervals in its group, so the returned intervals cover exactly the same points as the input.
- The input may contain duplicates and intervals nested inside others.
- Return the combined intervals in ascending order of `start`. No two returned intervals overlap, so this order is unique.
### Constraints
- `1 <= len(intervals) <= 10^5`
- Every interval has exactly two integers, and `-10^9 <= start <= end <= 10^9`.
- Every endpoint fits in a signed 32-bit integer; no value exceeds 2^31 - 1 (Java uses `int`, C++ uses `int`).
### Examples
**Example 1**
```text
Input: intervals = [[5, 7], [1, 4], [2, 3], [6, 9]]
Output: [[1, 4], [5, 9]]
```
`[2, 3]` lies inside `[1, 4]`. `[5, 7]` and `[6, 9]` overlap and combine into `[5, 9]`. `[1, 4]` and `[5, 9]` share no point, so they stay separate.
**Example 2**
```text
Input: intervals = [[3, 4], [1, 2], [4, 4]]
Output: [[1, 2], [3, 4]]
```
`[3, 4]` and `[4, 4]` share the point 4, so they combine into `[3, 4]`. `[1, 2]` and `[3, 4]` share no point, so they stay separate.
Constraints
- 1 <= len(intervals) <= 10^5
- Every interval has exactly two integers, and -10^9 <= start <= end <= 10^9.
- Every endpoint fits in a signed 32-bit integer; no value exceeds 2^31 - 1.
Examples
Input: ([[5, 7], [1, 4], [2, 3], [6, 9]],)
Expected Output: [[1, 4], [5, 9]]
Explanation: Source example 1: [2, 3] is nested in [1, 4]; [5, 7] and [6, 9] overlap into [5, 9].
Input: ([[3, 4], [1, 2], [4, 4]],)
Expected Output: [[1, 2], [3, 4]]
Explanation: Source example 2: the point interval [4, 4] touches [3, 4]; [1, 2] and [3, 4] are separated by a gap.
Hints
- Touching counts: [1, 4] and [4, 5] share the point 4 and must combine, while [1, 2] and [3, 4] share no point and stay separate.
- A group can grow through a chain of intervals, so two intervals that share no point may still end up in the same result.
- A group's end is the largest end among all of its members; an interval nested inside another must not pull that end back.