Merge Overlapping Closed Integer Intervals into a Sorted Disjoint List
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Given a list of closed integer intervals, merge every group of intervals that overlap and return the resulting disjoint intervals sorted by their start.
The candidate's report names this online-assessment question only as interval merging; this version fixes the exact rules below.
### Function Signature
```python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
```
### Rules
- Each interval is a pair `[start, end]` with `start <= end`. It covers every point from `start` to `end`, both ends included.
- Two intervals overlap when they share at least one point. Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 6]`, share the point 4 and are merged into `[1, 6]`. Intervals such as `[1, 4]` and `[5, 6]` share no point and stay separate.
- 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.
- The input may be in any order and may contain repeated intervals and intervals nested inside others.
- Each returned interval is `[start, end]`, where `start` is the smallest start and `end` the largest end in its merged group. No two returned intervals share a point.
- Return the merged intervals sorted by `start` ascending. An empty input returns `[]`.
### Constraints
- `0 <= len(intervals) <= 10^5`
- `-10^9 <= start <= end <= 10^9` for every interval
### Examples
**Example 1**
```text
Input: intervals = [[5, 7], [1, 3], [2, 4], [9, 9]]
Output: [[1, 4], [5, 7], [9, 9]]
```
`[1, 3]` and `[2, 4]` share the points 2 to 3 and merge into `[1, 4]`. `[5, 7]` starts after 4, so it stays separate, and the single-point interval `[9, 9]` overlaps nothing.
**Example 2**
```text
Input: intervals = [[1, 4], [4, 6], [6, 6], [0, 0]]
Output: [[0, 0], [1, 6]]
```
`[1, 4]` and `[4, 6]` share the point 4, and `[6, 6]` shares the point 6, so all three merge into `[1, 6]`. `[0, 0]` shares no point with them.
**Example 3**
```text
Input: intervals = [[2, 3], [1, 10], [11, 12], [4, 8]]
Output: [[1, 10], [11, 12]]
```
`[2, 3]` and `[4, 8]` lie inside `[1, 10]`. `[11, 12]` starts after 10 and shares no point with it.
Overview: An interval-merging coding question: given closed integer intervals in any order, merge every group that overlaps or touches at a shared endpoint and return the disjoint result sorted by start. It tests careful reasoning about nested, repeated and touching intervals and producing an efficient, exactly ordered result.
You are given a list of closed integer intervals. Each interval is a pair `[start, end]` with `start <= end`, and it covers every point from `start` to `end`, both ends included.
Two intervals **overlap** when they share at least one point. Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 6]`, share the point 4 and are merged into `[1, 6]`. Intervals such as `[1, 4]` and `[5, 6]` share no point and stay separate. 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.
The input may be in any order and may contain repeated intervals and intervals nested inside others.
Implement `merge_intervals(intervals)`, which merges every group of overlapping intervals and returns the resulting disjoint intervals:
- Each returned interval is `[start, end]`, where `start` is the smallest start and `end` is the largest end in its merged group. No two returned intervals share a point.
- Return the merged intervals sorted by `start` ascending.
- An empty input returns `[]`.
### Example 1
```text
Input: intervals = [[5, 7], [1, 3], [2, 4], [9, 9]]
Output: [[1, 4], [5, 7], [9, 9]]
```
`[1, 3]` and `[2, 4]` share the points 2 to 3 and merge into `[1, 4]`. `[5, 7]` starts after 4, so it stays separate, and the single-point interval `[9, 9]` overlaps nothing.
### Example 2
```text
Input: intervals = [[1, 4], [4, 6], [6, 6], [0, 0]]
Output: [[0, 0], [1, 6]]
```
`[1, 4]` and `[4, 6]` share the point 4, and `[6, 6]` shares the point 6, so all three merge into `[1, 6]`. `[0, 0]` shares no point with them.
### Constraints
- `0 <= len(intervals) <= 10^5`
- `-10^9 <= start <= end <= 10^9` for every interval
- Every input and output value lies within the signed 32-bit range (no value exceeds 2^31 - 1 in absolute value), so Java uses `int[][]` and C++ uses `std::vector<std::vector<int>>`.
Constraints
- 0 <= len(intervals) <= 10^5
- -10^9 <= start <= end <= 10^9 for every interval
- Every input and output value lies within the signed 32-bit range (no value exceeds 2^31 - 1 in absolute value)
Examples
Input: ([],)
Expected Output: []
Explanation: Empty input returns an empty list.
Input: ([[3, 8]],)
Expected Output: [[3, 8]]
Explanation: A single interval is returned unchanged.
Hints
- Intervals that only touch at one endpoint, such as [1, 4] and [4, 6], share that point and belong in the same merged interval.
- A merged interval ends at the largest end among all of its members, which is not necessarily the end of the member you looked at last: an interval can sit entirely inside another.
- The input may arrive in any order and merging is transitive, so a group can keep growing through a chain of intervals; make sure no remaining interval can still join a group before you report it.