Merge Overlapping or Touching Closed Intervals into a Sorted Disjoint List
Company: Fractal
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of closed intervals on the integer number line, merge every group of intervals that overlap or touch into a single interval, and return the resulting disjoint intervals sorted by their start.
The report identifies the problem only as a standard interval-merging exercise; this version fixes the exact merging and ordering rules in Rules below.
### Function Signature
```python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
```
### Rules
- Each element of `intervals` is a pair `[start, end]` with `start <= end`, describing every point `x` with `start <= x <= end`. An interval with `start == end` is a single point.
- Two intervals `[a, b]` and `[c, d]` share a point when `c <= b` and `a <= d`. Intervals that share a point belong to the same group, and so do intervals connected through a chain of such pairs.
- Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 6]`, share that point and are merged. Intervals such as `[1, 2]` and `[3, 4]` share no point and stay separate, even though no integer lies between them.
- Each group becomes one interval `[smallest start in the group, largest end in the group]`.
- The input may be in any order and may contain duplicate or nested intervals.
- Return the merged intervals as a list of `[start, end]` pairs in increasing order of `start`. Because the merged intervals are disjoint, this order is unique.
### Constraints
- `1 <= len(intervals) <= 10^5`
- `-10^9 <= start <= end <= 10^9`; every value fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: intervals = [[5, 8], [1, 3], [2, 4], [10, 12]]
Output: [[1, 4], [5, 8], [10, 12]]
```
`[1, 3]` and `[2, 4]` share the points from 2 to 3 and merge into `[1, 4]`. `[5, 8]` starts after 4, so it stays separate, and `[10, 12]` shares no point with any other interval.
**Example 2**
```text
Input: intervals = [[4, 7], [1, 4], [7, 7]]
Output: [[1, 7]]
```
`[1, 4]` and `[4, 7]` touch at 4, and the single point `[7, 7]` touches `[4, 7]` at 7, so all three intervals form one group.
**Example 3**
```text
Input: intervals = [[-3, 0], [2, 9], [-5, -4], [3, 5], [-4, -4]]
Output: [[-5, -4], [-3, 0], [2, 9]]
```
`[-4, -4]` touches `[-5, -4]` at -4, and `[3, 5]` lies inside `[2, 9]`. `[-3, 0]` starts after -4 and ends before 2, so it stays on its own.
Overview: Merge a list of closed integer intervals so that any intervals sharing at least one point, including intervals that only touch at an endpoint, become a single interval, then return the disjoint result sorted by start. Tests careful handling of unsorted input and of nested, touching and duplicate intervals, with an efficient solution for up to 10^5 intervals.
Given a list of closed intervals on the integer number line, merge every group of intervals that overlap or touch into a single interval, and return the resulting disjoint intervals sorted by their start.
Implement `merge_intervals(intervals)`, where `intervals` is a list of pairs `[start, end]`, and return a list of `[start, end]` pairs.
### Rules
- Each pair `[start, end]` has `start <= end` and describes every point `x` with `start <= x <= end`. An interval with `start == end` is a single point.
- Two intervals `[a, b]` and `[c, d]` share a point when `c <= b` and `a <= d`. Intervals that share a point belong to the same group, and so do intervals connected through a chain of such pairs.
- Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 6]`, share that point and are merged. Intervals such as `[1, 2]` and `[3, 4]` share no point and stay separate, even though no integer lies between them.
- Each group becomes one interval `[smallest start in the group, largest end in the group]`.
- The input may be in any order and may contain duplicate or nested intervals.
- Return the merged intervals as a list of `[start, end]` pairs in increasing order of `start`. Because the merged intervals are disjoint, this order is unique.
### Constraints
- `1 <= len(intervals) <= 10^5`
- `-10^9 <= start <= end <= 10^9`; every value fits in a 32-bit signed integer (no value exceeds 2^31 - 1, so Java and C++ use `int`).
### Example 1
```text
Input: intervals = [[5, 8], [1, 3], [2, 4], [10, 12]]
Output: [[1, 4], [5, 8], [10, 12]]
```
`[1, 3]` and `[2, 4]` share the points from 2 to 3 and merge into `[1, 4]`. `[5, 8]` starts after 4, so it stays separate, and `[10, 12]` shares no point with any other interval.
### Example 2
```text
Input: intervals = [[4, 7], [1, 4], [7, 7]]
Output: [[1, 7]]
```
`[1, 4]` and `[4, 7]` touch at 4, and the single point `[7, 7]` touches `[4, 7]` at 7, so all three intervals form one group.
Constraints
- 1 <= len(intervals) <= 10^5
- -10^9 <= start <= end <= 10^9 for every pair [start, end]; every value fits in a 32-bit signed integer (no value exceeds 2^31 - 1), so Java and C++ use int.
- The input may be in any order and may contain duplicate, nested, or single-point (start == end) intervals.
Examples
Input: ([[5, 8], [1, 3], [2, 4], [10, 12]],)
Expected Output: [[1, 4], [5, 8], [10, 12]]
Explanation: Source example 1: [1, 3] and [2, 4] overlap into [1, 4]; [5, 8] starts after 4 and [10, 12] is isolated.
Input: ([[4, 7], [1, 4], [7, 7]],)
Expected Output: [[1, 7]]
Explanation: Source example 2: [1, 4] and [4, 7] touch at 4 and the point [7, 7] touches [4, 7], so all three form one group.
Hints
- Two intervals [a, b] and [c, d] share a point exactly when c <= b and a <= d: touching at an endpoint counts, but [1, 2] and [3, 4] share nothing even though no integer lies between them.
- Grouping is transitive: two intervals that share no point with each other can still land in the same group through a third interval that overlaps both.
- A finished group is described only by its smallest start and its largest end, and the answer must list the groups in increasing order of start.