Part 2 · Problems · Intervals
Merge Intervals
#56 · Medium · LeetCode
Merge all overlapping intervals.
[[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]] [[1,4],[4,5]] -> [[1,5]]
Ask before coding
- Do touching intervals like [1,4],[4,5] merge?
- Is the input sorted?
Hint
After sorting by start, overlaps are neighbours.
Approach
Sort by start. For each interval, if it starts before the last merged one ends, extend the end. Otherwise start a new one.
Time O(n log n) Space O(n)
Watch it run
Solution (JavaScript, tested)
function mergeIntervals(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const out = [];
for (const [s, e] of sorted) {
const last = out[out.length - 1];
if (last && s <= last[1])
last[1] = Math.max(last[1], e); // overlap: extend
else out.push([s, e]);
}
return out;
}Traps
- Default sort() compares as strings. Always pass (a, b) => a[0] - b[0].
- Use max for the end ([1,4],[2,3] stays [1,4]).
Say out loud: Sorting by start puts overlapping intervals next to each other, then one pass merges them.