Merge Intervals
MediumIntervals
You get a list of intervals, each [start, end], in no particular order. Merge every group of overlapping intervals into one interval that covers them all, and return the intervals that are left.
Two intervals that only touch, like [5, 7] and [7, 9], overlap. The answer’s intervals can come back in any order.
Examples
Input: intervals = [[7, 12], [1, 4], [8, 9], [3, 5]] Output: [[1, 5], [7, 12]]
[1, 4] and [3, 5] overlap, and [8, 9] lies wholly inside [7, 12].
Input: intervals = [[5, 7], [7, 9]] Output: [[5, 9]]
They touch at 7, which counts as overlapping.
Constraints
1 ≤ intervals.length ≤ 10⁴0 ≤ start ≤ end ≤ 10⁴
Stuck?
Hint 1
Sort the intervals by start. Then each one either overlaps the last interval you kept, or begins a new one.
Hint 2
When it overlaps, stretch the last kept interval’s end to the larger of the two ends, not simply to the new interval’s end: it may sit entirely inside.
The idea
Once the intervals are sorted by start, intervals that overlap sit next to each other. Walk through them keeping the interval you are building: each new one either overlaps it and stretches it, or starts after it ends and begins the next one.
Time O(n log n)Extra space O(n) for the answer
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Sort a copy by start. After this, an interval can only overlap the group being built, never one that was finished earlier.
function merge(intervals) { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); const answer = []; for (const [start, end] of sorted) { const last = answer[answer.length - 1]; if (last && start <= last[1]) last[1] = Math.max(last[1], end); else answer.push([start, end]); } return answer;}The trap
Setting the end to the new interval's end works whenever intervals are sorted by start and each one ends later than the last, which is the usual picture. When an interval sits entirely inside the one before it, the end shrinks, so the merged interval comes out too short. Any later interval that overlaps only the cut-off part is then split off on its own.
function merge(intervals) { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); const answer = []; for (const [start, end] of sorted) { const last = answer[answer.length - 1]; if (last && start <= last[1]) last[1] = end; // shrinks it when the new one sits inside else answer.push([start, end]); } return answer;}