Merge Intervals
Sort by start. Extend the last interval while the next one starts before it ends, otherwise push a new one.
IntervalsO(n log n)New10 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
overlapping ranges
merge or insert an interval
free time / conflicts
The template
Get this into muscle memory, then adapt the condition per problem.
intervals.sort((a, b) => a[0] - b[0]);
const out = [intervals[0]];
for (const [s, e] of intervals.slice(1)) {
const last = out[out.length - 1];
if (s <= last[1]) last[1] = Math.max(last[1], e);
else out.push([s, e]);
}If you are stuck
The generic hint ladder for this pattern, in order.
- 1Unsorted intervals make overlap hard to reason about. Fix that first.
- 2After sorting by start, only the previous interval can overlap the current one.
- 3Extend with max of the two ends, not just the new end.
Drill it
Every problem in the bank that uses this pattern.
0 / 10 solved