March 24
Merge Intervals
How to sort by start time and turn many intervals into one pass that either expands the current block or opens a new one.
Intervals Intermediate 20 min TypeScript
Given an array of intervals intervals, where intervals[i] = [starti, endi], merge all overlapping intervals and return the resulting array.
Intervals that touch also count as overlapping.
Example:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
What to notice before coding
- After sorting by start, the only relevant overlap is with the last merged interval.
- If two intervals touch, like `[1,4]` and `[4,5]`, they still become one block.
- During a merge, what usually changes is the end of the interval.
Common mistakes
- forgetting to sort before the pass
- replacing the end directly instead of using `max`
Step 1 - Write the baseline that naturally appears
If you do not know the pattern yet, the tendency is:
- take one interval
- compare it with every block you already merged
- decide whether it fits into one of them
It works.
But it creates too many comparisons.
Step 2 - Ask which comparison actually matters
The problem is not asking you to detect overlap in random order.
It asks you to consolidate everything at the end.
If the intervals are sorted by start, the only real candidate for overlap is the last interval in the answer.
Step 3 - Understand the merge rule
For two intervals:
- if
currentStart <= lastEnd, they overlap - the start of the merged block stays the same
- the end becomes
max(lastEnd, currentEnd)
Otherwise, you open a new block.
Step 4 - Turn that into a linear sweep
After sorting, the pass becomes simple:
- if it overlaps, expand
- if it does not overlap, add a new one
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function merge(intervals: number[][]): number[][] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n log n)
Space: O(n)
Solution 1 - Compare against all existing merged blocks in O(n²)
Good baseline to make the extra work visible.
export function merge(intervals: number[][]): number[][] {
const merged: number[][] = []
for (const [start, end] of intervals) {
let currentStart = start
let currentEnd = end
const nextMerged: number[][] = []
for (const [mergedStart, mergedEnd] of merged) {
const overlaps = currentStart <= mergedEnd && mergedStart <= currentEnd
if (overlaps) {
currentStart = Math.min(currentStart, mergedStart)
currentEnd = Math.max(currentEnd, mergedEnd)
} else {
nextMerged.push([mergedStart, mergedEnd])
}
}
nextMerged.push([currentStart, currentEnd])
nextMerged.sort((a, b) => a[0] - b[0])
merged.length = 0
merged.push(...nextMerged)
}
return merged
}Correct, but too messy for a problem that quickly drifts toward O(n²).
Solution 2 - Sort + linear sweep in O(n log n)
Now the local rule becomes clear.
export function merge(intervals: number[][]): number[][] {
if (intervals.length === 0) {
return []
}
const sorted = [...intervals].sort((a, b) => a[0] - b[0])
const merged = [sorted[0].slice()]
for (let index = 1; index < sorted.length; index += 1) {
const [currentStart, currentEnd] = sorted[index]
const lastMerged = merged[merged.length - 1]
if (currentStart <= lastMerged[1]) {
lastMerged[1] = Math.max(lastMerged[1], currentEnd)
} else {
merged.push([currentStart, currentEnd])
}
}
return merged
}The trick is not memorizing Merge Intervals. It is noticing that sorting turns a global problem into one repeated local decision.
What to say in the interview
A strong short explanation would be:
Without sorting, I end up comparing each interval against many merged blocks. Once I sort by start, I only need to inspect the last consolidated interval. If there is overlap, I expand the end. If there is no overlap, I open a new block. The overall cost becomes
O(n log n)because of the sort.
That shows that you:
- used structure before iterating
- reduced comparisons in a justified way
- explained the merge rule clearly
When this pattern shows up again
The same pattern comes back when you need to:
- sort and sweep
- consolidate overlapping blocks
- compare the current state only with the latest valid state
- solve meeting rooms, insert interval, and similar variants
The point is not memorizing
merge.
The point is learning when sorting removes the need to compare against everybody.