Topic · IntervalsMedium
Merge Intervals
Understand the problem
Given a list of intervals intervals[i] = [start, end].
Merge all overlapping intervals and return a list of non-overlapping intervals.
ts
intervals = [[1,3],[2,6],[8,10],[15,18]]
output = [[1,6],[8,10],[15,18]]
// [1,3] and [2,6] overlap (2 <= 3) → merged into [1,6]Main idea: sort by start first.
Once sorted, an interval can only overlap the one most recently added to the result — so you only compare with the last element, not every pair.
Basic approach
O(n²) time or worsets
function mergeNaive(intervals: number[][]): number[][] {
const used = new Array(intervals.length).fill(false)
const result: number[][] = []
for (let i = 0; i < intervals.length; i++) {
if (used[i]) continue
let [start, end] = intervals[i]
let changed = true
while (changed) { // rescan everything for overlapping intervals to merge
changed = false
for (let j = 0; j < intervals.length; j++) {
if (used[j] || j === i) continue
const [s, e] = intervals[j]
if (s <= end && start <= e) {
start = Math.min(start, s); end = Math.max(end, e)
used[j] = true; changed = true
}
}
}
result.push([start, end])
}
return result
}Why this approach is slow:
Without sorting, every interval must be compared with every other, repeatedly.
Sorting first reduces the problem to a single pass, O(n log n) overall.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.