Merge Overlapping Closed Intervals Into a Sorted Disjoint List
Company: Furtherai
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a list of closed integer intervals, merge every group of overlapping intervals and return the resulting disjoint intervals.
### Function Signature
```python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
```
Each interval is `[start, end]` with `start <= end`, and it contains every point from `start` to `end`, inclusive.
### Rules
- The input may be in any order, and it may contain duplicate intervals and intervals nested inside others.
- Two intervals overlap when they share at least one point. Intervals that only touch, such as `[1, 3]` and `[3, 5]`, share the point 3 and must be merged into `[1, 5]`. The intervals `[1, 2]` and `[3, 4]` 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.
- Return the merged intervals sorted by `start` in ascending order. No two returned intervals share a point, and together they cover exactly the points covered by the input.
### Constraints
- `1 <= len(intervals) <= 10^5`
- `-10^9 <= start <= end <= 10^9`
### Examples
**Example 1**
```text
Input: intervals = [[8, 10], [1, 4], [3, 6], [12, 12]]
Output: [[1, 6], [8, 10], [12, 12]]
```
`[1, 4]` and `[3, 6]` overlap on 3 to 4 and become `[1, 6]`. `[8, 10]` and the single point `[12, 12]` overlap nothing.
**Example 2**
```text
Input: intervals = [[1, 3], [3, 5], [6, 7]]
Output: [[1, 5], [6, 7]]
```
`[1, 3]` and `[3, 5]` touch at 3, so they merge. `[1, 5]` and `[6, 7]` share no point.
**Example 3**
```text
Input: intervals = [[2, 9], [3, 4], [5, 5], [1, 2]]
Output: [[1, 9]]
```
`[3, 4]` and `[5, 5]` lie inside `[2, 9]`, and `[1, 2]` touches it at 2.
Overview: A coding question that merges an unsorted list of closed integer intervals into disjoint intervals sorted by start. Intervals that overlap or merely touch at an endpoint must be combined, so it tests exact endpoint semantics, transitive merges, and nested or duplicate intervals.
Read the full Furtherai Machine Learning Engineer interview experience this question came from
Given a list `intervals` of closed integer intervals, merge every group of overlapping intervals and return the resulting disjoint intervals.
Each interval is a pair `[start, end]` with `start <= end`, and it contains every point from `start` to `end`, inclusive.
### Rules
- The input may be in any order, and it may contain duplicate intervals and intervals nested inside others.
- Two intervals overlap when they share at least one point. Intervals that only touch, such as `[1, 3]` and `[3, 5]`, share the point 3 and must be merged into `[1, 5]`. The intervals `[1, 2]` and `[3, 4]` 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.
- Return the merged intervals as a list of `[start, end]` pairs sorted by `start` in ascending order. No two returned intervals share a point, and together they cover exactly the points covered by the input.
### Constraints
- `1 <= len(intervals) <= 10^5`
- `-10^9 <= start <= end <= 10^9` for every interval
- Every input and output value lies within `[-10^9, 10^9]`, so no value exceeds 2^31-1 and 32-bit integers suffice in every language.
### Examples
**Example 1**
```text
Input: intervals = [[8, 10], [1, 4], [3, 6], [12, 12]]
Output: [[1, 6], [8, 10], [12, 12]]
```
`[1, 4]` and `[3, 6]` overlap on 3 to 4 and become `[1, 6]`. `[8, 10]` and the single point `[12, 12]` overlap nothing.
**Example 2**
```text
Input: intervals = [[1, 3], [3, 5], [6, 7]]
Output: [[1, 5], [6, 7]]
```
`[1, 3]` and `[3, 5]` touch at 3, so they merge. `[1, 5]` and `[6, 7]` share no point.
Constraints
- 1 <= len(intervals) <= 10^5
- -10^9 <= start <= end <= 10^9 for every interval [start, end]
- Every input and output value fits in a signed 32-bit integer (no value exceeds 2^31-1)
Examples
Input: ([[8, 10], [1, 4], [3, 6], [12, 12]],)
Expected Output: [[1, 6], [8, 10], [12, 12]]
Explanation: Source Example 1: [1, 4] and [3, 6] overlap; [8, 10] and the point [12, 12] stay separate; input is unsorted.
Input: ([[1, 3], [3, 5], [6, 7]],)
Expected Output: [[1, 5], [6, 7]]
Explanation: Source Example 2: touching endpoints at 3 merge; 5 and 6 share no point.
Hints
- Overlap means sharing at least one point: intervals that meet at a single endpoint overlap, while [1, 2] and [3, 4] do not.
- Merging is transitive, so one interval can connect two others that never overlap each other directly.
- An interval nested inside another can end before the outer one does; the merged result must still reach the outer interval's end.