Learn › DSA Patterns › Merge Intervals

Pattern #7 · Intervals · O(N log N) Time O(N) Space

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.

🧱 Merge overlaps ➕ Insert into sorted ✂️ Intersect two lists
Scroll to learn

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:

1–3 first meeting → open block 1–3
2–6 2 ≤ 3, overlaps → stretch to 1–6
8–10 8 > 6, gap → close 1–6, open 8–10
15–18 15 > 10, gap → close 8–10, open 15–18
result busy 1–6, 8–10, 15–18 ✓

🚀

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.

blocks: 0
input merged 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Input arrives unsorted: [[8,10],[1,3],[15,18],[2,6]].

waiting being checked processed merged block
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.

🐛 Forgetting to sort

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.

🐛 Sorting without a comparator

[[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.

🐛 Overwriting the end instead of taking the max

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.

🧱 Merge (LC 56) sort, then sweep
Input Any order
First step Sort by start
Compare against The last merged block
Overlap test start <= last[1]
Time O(N log N)
➕ Insert (LC 57) three zones
Input Sorted, non-overlapping
First step None — trust the order
Compare against The one new interval
Zone tests end < s / start > e
Time O(N)
You can solve Insert by appending the new interval and running Merge. It's correct — and it's O(N log N) for order you already had. In an interview, mention it as the fallback, then write the single pass.

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 study
M3 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

Question 1 of 9 Score: 0
What is the first step of the classic Merge Intervals solution (LeetCode 56), and why is it needed? basic

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.