Merge Overlapping Intervals
Company: ByteDance
Role: Senior SDE, Quality Platform & AI Test Automation
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given intervals sorted by start value, merge every pair of overlapping intervals and return the resulting non-overlapping intervals in ascending start order. Intervals that touch at one endpoint are considered overlapping.
### Function Contract
Implement `merge_intervals(intervals) -> list[list[int]]`. The input must not be mutated.
### Constraints
- `1 <= len(intervals) <= 200000`.
- Each interval is `[start, end]` with `start <= end`.
- Input intervals are already sorted by nondecreasing start.
- Endpoints lie in `[-10^9, 10^9]`.
### Examples
- `[[1,3],[2,6],[8,10],[15,18]]` returns `[[1,6],[8,10],[15,18]]`.
- `[[1,10],[2,3]]` returns `[[1,10]]`; the inner interval must not shrink the result.
```hint Compare with the last merged interval
When the next start is within the last merged range, extend its end with the maximum of both ends.
```
### Edge Cases
- One interval is returned unchanged.
- Fully contained intervals do not change the merged end.
- A chain of pairwise overlaps becomes one interval.
Overview: Merge start-sorted closed intervals in one pass, treating touching endpoints as overlap and ensuring contained intervals never shrink the accumulated range.
Given closed intervals already sorted by nondecreasing start, merge every overlapping pair and return the resulting non-overlapping intervals in ascending start order. Intervals that touch at an endpoint overlap. Do not mutate the input.
Constraints
- 1 <= len(intervals) <= 200000.
- Each interval is `[start, end]` with `start <= end`.
- Intervals are sorted by nondecreasing start.
- Endpoints are in [-1000000000, 1000000000].
Examples
Input: ([[1, 3], [2, 6], [8, 10], [15, 18]],)
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: The first two source-example intervals overlap; the others remain disjoint.
Input: ([[1, 10], [2, 3]],)
Expected Output: [[1, 10]]
Explanation: A contained interval does not shrink the outer interval.
Hints
- Compare each interval only with the last interval already placed in the result.
- On overlap, take the maximum end so a contained interval cannot shrink the merged range.