Merge Intervals
Given an array of intervals where intervalsi = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover every interval in the input. Sort the intervals by start time first — once they are sorted, any interval that overlaps the current one must come immediately after it, so a single linear scan is enough to merge them.
Constraints
- 0 ≤ intervals.length ≤ 104
- intervalsi.length == 2
- 0 ≤ starti ≤ endi ≤ 105
Example
Input
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]Output
[[1, 6], [8, 10], [15, 18]]Explanation [1, 3] and [2, 6] overlap, so they merge into [1, 6].
In plain terms
- Overlapping intervals
- Two intervals overlap when one starts before or exactly when the other ends — for example, [1, 4] and [4, 5] overlap at 4.
Sort by start, then merge overlapping intervals in one pass
01-3
12-6
28-10
315-18
Statusinit
Sorted by start. Current interval starts as [1, 3].
What happens in this step
sorted = [[1, 3], [2, 6], [8, 10], [15, 18]] (already sorted by start) result = [sorted[0].slice()] = [[1, 3]] The first interval seeds result as the current "last" interval — nothing to compare against yet.
Step 1 of 5
Steps to visualize
- Sort the intervals by start time.
- Keep a "current" merged interval, starting with the first one.
- For each next interval, if its start is ≤ the current interval's end, they overlap — extend the current interval's end.
- Otherwise the current interval is finished — save it and start a new current interval.
- Save the last current interval once the scan ends.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
01-3
12-6
28-10
315-18
Statusinit
Sorted by start. Current interval starts as [1, 3].
What happens in this step
sorted = [[1, 3], [2, 6], [8, 10], [15, 18]] (already sorted by start) result = [sorted[0].slice()] = [[1, 3]] The first interval seeds result as the current "last" interval — nothing to compare against yet.
Step 1 of 5
Solution
function mergeIntervals(intervals) {
if (intervals.length === 0) return [];
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const result = [sorted[0].slice()];
for (let i = 1; i < sorted.length; i++) {
const current = sorted[i];
const last = result[result.length - 1];
if (current[0] <= last[1]) {
last[1] = Math.max(last[1], current[1]);
} else {
result.push(current.slice());
}
}
return result;
}- Time
- O(n log n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] | [[1, 6], [8, 10], [15, 18]] | example from the docstring |
intervals = [[1, 2], [3, 4]] | [[1, 2], [3, 4]] | intervals with no overlap stay separate |
intervals = [[1, 10], [2, 3]] | [[1, 10]] | one interval fully contains another |
intervals = [[1, 4], [4, 5]] | [[1, 5]] | intervals that touch exactly at an endpoint still merge |
intervals = [[5, 7]] | [[5, 7]] | smallest valid input, a single interval |
intervals = [] | [] | no intervals to merge |
intervals = [[5, 7], [1, 3]] | [[1, 3], [5, 7]] | input arrives out of start-time order |
intervals = [[1, 4], [2, 5], [3, 6], [10, 12]] | [[1, 6], [10, 12]] | a chain of overlapping intervals collapses into one |