Given a list of intervals where each intervals[i] = [start, end], merge every pair of overlapping intervals and return the resulting non-overlapping intervals.
Two intervals overlap when one starts at or before the other ends (touching endpoints such as [1, 4] and [4, 5] count as overlapping). Return the merged intervals sorted in ascending order of start.
Example
[1,3] and [2,6] overlap, so they merge into [1,6]; the rest stay separate.
Constraints
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start <= end <= 10^4
Intuition
A first pass treats merging as a repeated scan: keep sweeping the whole list, and whenever two intervals overlap, fuse them into one and start over — repeating until a full pass makes no change.
function merge(intervals) {
const result = intervals.map((iv) => [...iv]); // work on a copy
let merged = true;
// Keep looping until a whole pass finds nothing left to fuse.
while (merged) {
merged = false;
outer:
for (let i = 0; i < result.length; i++) {
for (let j = i + 1; j < result.length; j++) {
// Two intervals overlap if neither ends before the other starts.
if (result[i][0] <= result[j][1] && result[j][0] <= result[i][1]) {
// Fuse j into i, drop j, and restart the scan.
result[i] = [Math.min(result[i][0], result[j][0]), Math.max(result[i][1], result[j][1])];
result.splice(j, 1);
merged = true;
break outer;
}
}
}
}
return result.sort((a, b) => a[0] - b[0]); // present in start order
}Re-scanning the whole list after every fuse is O(n²) work — far more than necessary. Can we do better?
The key observation: if the intervals are sorted by start, then any interval that overlaps a given one must come right after it — so a single left-to-right pass is enough. We never have to look backward, because everything earlier already starts no later.
So sort by start, then sweep while holding only the last interval in the output as a running frontier. For each next interval: if its start is at or before the frontier's end they overlap, so widen the frontier's end to the larger of the two; otherwise there's a gap, so push it as a new frontier.
Walking it through:
sorted by start: [[1, 3], [2, 6], [8, 10], [15, 18]]
The first interval seeds the frontier — there's nothing before it to overlap.
[2,6] starts at 2, within the frontier's end 3, so they overlap. Frontier widens to [1, 6].
[8,10] starts past the frontier's end 6, so it's disjoint. output = [[1, 6], [8, 10]].
[15,18] clears the frontier 10 as well, so it becomes its own interval.
One pass over the sorted list collapsed four intervals into three non-overlapping ranges.
Optimization
Sort then sweep
Sort the intervals by start. Walk left to right keeping the last interval in the output: if the current interval starts at or before that interval's end, extend the end to the larger of the two ends; otherwise it's disjoint, so push it as a new output interval.
O(n log n) time (the sort dominates), O(n) extra space for the output.
function merge(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const result = [];
for (const [start, end] of sorted) {
const last = result[result.length - 1];
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end);
} else {
result.push([start, end]);
}
}
return result;
}Complexity analysis
Time complexity: O(n log n). Here's why:
- Sorting the
nintervals by start takes O(n log n). - The sweep that follows visits each interval once, doing O(1) work per step — O(n).
The sort dominates the linear sweep, so the overall time is O(n log n), where n is the number of intervals.
Space complexity: O(n). Here's why:
- We sort a copy of the input rather than mutating the caller's array — O(n).
- The sweep keeps only a reference to the last output interval — O(1) beyond the output.
The merged output isn't counted as auxiliary space; in the worst case (nothing overlaps) it holds all n intervals.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| intervals = [] | [] | Empty input — nothing to merge. |
| intervals = 14 | [[1,4]] | A single interval passes through unchanged. |
| intervals = 14 45 | [[1,5]] | Touching endpoints count as overlapping (closed intervals). |
| intervals = 110 23 45 | [[1,10]] | Fully nested intervals are absorbed without widening the frontier. |
| intervals = 13 13 24 | [[1,4]] | Duplicate intervals collapse, then [2,4] extends the end. |
| intervals = 810 13 56 | [[1,3],[5,6],[8,10]] | Unsorted, already-disjoint input — sort decides the output order. |
Try it yourself
Write your solution against the real judge before checking the reference.