Learn › DSA Patterns › Merge Intervals
Merge
Intervals
Anything with a start and an end — meetings, sessions, IP ranges — collapses the same way. Sort by start, then walk the list once, either stretching the current block or starting a new one.
Story Time
The Overbooked Calendar 📅
Before writing a single line of code, let's understand the intuition through a story.
Arjun Gets Asked "When Are You Busy?"
A client wants a call tomorrow. Arjun's calendar has four bookings, entered in whatever order they came in: 8–10, 1–3, 15–18 and 2–6. The client doesn't want four meetings. They want his busy blocks.
The Exhausting Way
Compare every meeting against every other one, merge any pair that overlaps, and repeat until nothing changes. Four meetings means six pairs. A hundred means 4,950 pairs — per round. That's O(N²) at best, and a merge can create a new overlap you have to go back and catch.
What He Actually Does
He lines the meetings up by start time: 1–3, 2–6, 8–10, 15–18. Now he only ever compares a meeting with the block he's currently building. Overlaps it? Stretch the block. Starts after it ends? That block is finished for good — nothing later can reach back to it.
- ✗ Compare every pair → O(N²)
- ✓ Sort once, sweep once → O(N log N)
Four Meetings, Three Blocks
After sorting, the sweep makes one decision per meeting:
🚀
Moral of the story
Sorting by start turns "does anything overlap anything?" into "does this one overlap the last block?" One question per interval, asked once.
Interactive
Merge Visualizer
Merge [[8,10],[1,3],[15,18],[2,6]] — unsorted,
exactly as Arjun's calendar had it.
Input arrives unsorted: [[8,10],[1,3],[15,18],[2,6]].
sort((a, b) => a[0] - b[0]) Line everything up by start start <= last[1] → stretch Overlaps the block — extend it start > last[1] → push Gap — that block is final Complexity
Three Approaches
| Approach | Time | Space | Best for |
|---|---|---|---|
| Pairwise, repeat until stable | O(N²)+ | O(N) | Nothing — it's the baseline to beat |
| Sort + Sweep Default ✓ | O(N log N) | O(N) | Unsorted input (LC 56) |
| Single pass, no sort | O(N) | O(N) | Input already sorted (LC 57, LC 986) |
The sort is the whole cost. That's why the first question to ask about any interval problem is "is the input already sorted?" If it is, re-sorting it throws away a guarantee you were handed for free — the Insert Interval case study shows the O(N) version.
TypeScript
Implementation
Merge → insert into sorted → intersect two lists.
// Merge Intervals — O(N log N) time, O(N) space
// LeetCode 56 — Merge Intervals
function merge(intervals: number[][]): number[][] {
// Copy first: sort() mutates, and the caller's array isn't ours to reorder.
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const merged: number[][] = [];
for (const [start, end] of sorted) {
const last = merged[merged.length - 1];
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end); // overlap: stretch the block
} else {
merged.push([start, end]); // gap: start a new block
}
}
return merged;
}
console.log(merge([[1,3],[2,6],[8,10],[15,18]])); // → [[1,6],[8,10],[15,18]]
console.log(merge([[1,4],[4,5]])); // → [[1,5]]
Every output in these comments came from actually running the code, not from reading it.
Want the step-by-step reasoning behind insert(),
plus three one-character edits that break it? Read the
Insert Interval case study.
Gotchas
Three Bugs That Pass Small Tests
Each broken variant below was run in Node. The wrong output is what it actually printed.
merge, sort step deleted: [[8,10],[1,3],[2,6]]
→ [[8,10]]
want [[1,6],[8,10]]
[1,3] and [2,6] both pass start <= 10 against the [8,10] block, so they're swallowed into it. The sweep only works if blocks arrive in start order.
[[10,20],[9,15],[2,3]].sort()
→ [[10,20],[2,3],[9,15]]
want [[2,3],[9,15],[10,20]]
With no comparator, sort() compares strings: "10,20" < "2,3" < "9,15". Every test with single-digit values passes. The first 10 breaks it.
merge with last[1] = end: [[1,10],[2,3]]
→ [[1,3]]
want [[1,10]]
Sorting by start says nothing about ends. [2,3] sits entirely inside [1,10], and plain assignment shrinks the block. Use Math.max(last[1], end).
Comparison
Merge vs Insert
Same idea — absorb anything that overlaps — but one is handed sorted input and one isn't.
Pattern Recognition
Spot the Disguise
Interval problems rarely say "interval." The test: does each item have a start and an end, and does the question care whether those spans touch?
Said out loud
Easy to spot — the word "interval" is in the prompt.
- Merge all overlapping intervals LC 56
- Insert a new interval and merge LC 57
- Intersect two interval lists LC 986
- Remove one interval from a set LC 1272
Dressed as scheduling
The most common interview framing.
- Can one person attend every meeting? LC 252
- How many meeting rooms are needed? LC 253
- Find a slot that works for two people LC 1229
- Book an event only if it doesn't double-book LC 729
Dressed as "remove the fewest"
Greedy, and usually sorted by end, not start.
- Remove the fewest intervals so none overlap LC 435
- Fewest arrows to burst every balloon LC 452
Dressed as real-world data
No LeetCode number — just a spec from work.
- Stitch login sessions into continuous online time
- Collapse IP or port ranges in a firewall rule set
- Track which number ranges a stream has covered LC 352
- Add, remove and query tracked ranges LC 715
Does touching count? It depends on the problem.
The algorithm barely changes between these problems. The comparison operator does — and it's the single most common bug in interval code.
| Problem | Touching endpoints | Check | Example |
|---|---|---|---|
| LC 56 Merge Intervals | Merge | start <= last[1] | [1,4] + [4,5] → [1,5] |
| LC 57 Insert Interval | Merge | end < s / start > e | [1,4] + [4,6] → [1,6] |
| LC 452 Burst Balloons | One arrow covers both | start <= arrow | [1,2], [2,3] → 1 arrow |
| LC 252/253 Meeting Rooms | No clash | start < prevEnd | [5,10], [10,15] → 1 room |
| LC 435 Non-overlapping | No clash | start < prevEnd | [1,2], [2,3] → keep both |
Practice
Solve It Yourself
Click any question to see hints and approach.
B Basic
B1 What is the Merge Intervals pattern, and why does it start with a sort? ⌄
💡 Hint
After sorting by start, ask: which earlier intervals could the current one possibly overlap?
✅ Answer
Sort intervals by start, then walk them once, keeping a list of merged blocks. Each interval either overlaps the last block (stretch it) or starts after it (push a new block). Sorting is what guarantees only the last block matters — any earlier block ended before the last one began, so it ends before the current interval begins too. Cost: O(N log N) for the sort, O(N) for the sweep.
B2 Trace merge([[1,3],[2,6],[8,10],[15,18]]) step by step. ⌄
💡 Hint
Already sorted. Keep one running block and compare each new start against its end.
✅ Answer
[1,3] → push, blocks [[1,3]]. [2,6]: 2 ≤ 3 → stretch to max(3,6)=6, blocks [[1,6]]. [8,10]: 8 > 6 → push, [[1,6],[8,10]]. [15,18]: 15 > 10 → push. Result [[1,6],[8,10],[15,18]].
B3 Why does [[1,4],[4,5]] merge into [[1,5]] in LeetCode 56? ⌄
💡 Hint
Reread the problem's definition of overlap. Then look at whether your check uses < or <=.
✅ Answer
Closed intervals that share an endpoint overlap — [1,4] and [4,5] both contain 4. The check must be start <= last[1]. With start < last[1], 4 < 4 is false and you'd return [[1,4],[4,5]].
M Intermediate
M1 LeetCode 56 — Merge Intervals: merge [[1,3],[2,6],[8,10],[15,18]]. ⌄
💡 Hint
Sort by start with an explicit comparator, then sweep with one running block.
✅ Answer
[[1,6],[8,10],[15,18]]. Remember the three traps: sort first, pass (a, b) => a[0] - b[0] rather than relying on the default string sort, and stretch with Math.max(last[1], end) so a contained interval can't shrink the block.
→ Solve on LeetCode ↗M2 LeetCode 57 — Insert Interval: insert [4,8] into [[1,2],[3,5],[6,7],[8,10],[12,16]]. ⌄
💡 Hint
The input is already sorted. Every interval is either fully left of [4,8], fully right of it, or overlapping it.
✅ Answer
[[1,2],[3,10],[12,16]]. Left: end < newStart. Right: start > newEnd. Everything else stretches newStart with min and newEnd with max. [8,10] touches at 8, and 8 > 8 is false, so it's absorbed. One O(N) pass, no sort.
→ Read the full case studyM3 LeetCode 986 — Interval List Intersections: intersect [[0,2],[5,10],[13,23],[24,25]] with [[1,5],[8,12],[15,24],[25,26]]. ⌄
💡 Hint
Two sorted lists, two pointers. The overlap of two intervals is [later start, earlier end]. Which pointer is safe to advance?
✅ Answer
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]. Compute lo = max(starts), hi = min(ends), keep it if lo <= hi. Advance whichever interval ends first — it can't intersect anything later in the other list. O(M + N), no sort.
→ Solve on LeetCode ↗H Advanced
H1 LeetCode 435 — Non-overlapping Intervals: how many must you remove from [[1,2],[2,3],[3,4],[1,3]] so the rest don't overlap? ⌄
💡 Hint
This one treats [1,2] and [2,3] as fine together. And it's greedy: which interval leaves the most room for everything after it?
✅ Answer
1 (drop [1,3]). Sort by END, not start. Keep an interval if it starts at or after the last kept end; otherwise remove it. Keeping whichever finishes first blocks the fewest future intervals. Note the check here is start < prevEnd — touching is allowed.
→ Solve on LeetCode ↗H2 LeetCode 253 — Meeting Rooms II: how many rooms does [[0,30],[5,10],[15,20]] need? ⌄
💡 Hint
Merging tells you when anyone is busy, not how many meetings run at once. You need the peak number of simultaneous meetings.
✅ Answer
2. Sort starts [0,5,15] and ends [10,20,30] separately. Sweep the starts: if a start comes before the earliest unused end, you need a new room; otherwise a room has freed up. Equivalent: a min-heap of end times. O(N log N). [0,30] overlaps both others, but [5,10] and [15,20] never overlap each other.
→ Solve on LeetCode ↗H3 LeetCode 452 — Minimum Number of Arrows to Burst Balloons: [[10,16],[2,8],[1,6],[7,12]]. ⌄
💡 Hint
It's 435 in disguise, but touching counts here: an arrow at x = 2 bursts both [1,2] and [2,3].
✅ Answer
2. Sort by end: [1,6],[2,8],[7,12],[10,16]. Shoot at 6 — that bursts [1,6] and [2,8]. [7,12] starts after 6, so shoot at 12, which also gets [10,16]. New arrow only when start > arrow position.
→ Solve on LeetCode ↗In the Wild
Real-World Applications
Scheduling Tools
Finding a Free Slot
To offer a meeting time across five attendees, a scheduler collects every busy block from every calendar. Merged, they become a short list of busy stretches. The gaps between them are the free slots.
🔍 How it fits: Exactly LeetCode 56 followed by reading the gaps — the same shape as Employee Free Time (LC 759).
PostgreSQL
range_agg and Multiranges
Since PostgreSQL 14, range_agg() collapses a column of ranges — booking dates, price bands — into one multirange. Overlapping and adjacent ranges come out merged, so you can store bookings and ask for occupied periods in SQL.
🔍 How it fits: A multirange is a normalized list of disjoint ranges — the output of Merge Intervals, kept as a data type.
Web Browsers
video.buffered
An HTML media element's buffered property returns a TimeRanges object listing which seconds of the video have downloaded. The spec requires it normalized: sorted, non-overlapping, with touching ranges folded together.
🔍 How it fits: Every new chunk the player fetches is an Insert Interval into an already-sorted, already-merged list.
Genomics
bedtools merge
Bioinformaticians merge overlapping genomic features — reads, peaks, exons — with bedtools merge, which combines overlapping and book-ended intervals into one. It requires input sorted by chromosome and start first.
🔍 How it fits: Sort, then sweep. The 'sort your BED file first' rule is the sort step of LeetCode 56.
Quick Reference
Cheat Sheet
The Patterns
Sort (always a comparator)
sort((a, b) => a[0] - b[0]) Overlaps the last block?
start <= last[1] Stretch
last[1] = max(last[1], end) Insert zones
end < s | start > e Intersection of two
[max(starts), min(ends)] When to Use
- ✓ Items have a start and an end
- ✓ "Overlapping", "conflict", "busy"
- ✓ Merge or consolidate ranges
- ✓ Insert into a sorted range list
- ✓ Free time / gaps between ranges
- ✓ Intersect two range lists
- ✓ Fewest removals to stop overlaps
- ✓ Peak concurrent ranges (rooms)
Rules
Sorted already?
Skip the sort. One pass, O(N).
Merging? Sort by start.
Removing or scheduling greedily? Sort by end.
Reread "overlap"
Does touching count? That's < vs <=.
Complexity
Time: O(N log N) with a sort, O(N) without
Space: O(N) for the output
Test Yourself
Quiz: Check Your Understanding
Your score
0 / 9
Keep Learning
You've mastered Merge Intervals 🎉
Calendars, database ranges, video buffers, genome files — all of them collapse with one sort and one sweep.
Next, while the pattern is warm: LeetCode 435 — Non-overlapping Intervals, then LeetCode 452 — Minimum Number of Arrows and LeetCode 729 — My Calendar I.