Skip to content

024 — Merge Intervals

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

24 — Merge Intervals

🍽️ Intuition

The Arrays and Strings chapter covered the data structure itself — an ordered, indexable sequence, here holding [[Int]] interval pairs. This chapter is about recognizing when sorting that array first turns an all-pairs overlap check into a single left-to-right sweep.

Picture a shared conference room's booking sheet for the day, written as a list of [start, end] time slots submitted in no particular order: 2:00–3:00, 9:00–10:30, 2:30–4:00, 10:00–11:00. Before you can print a clean daily schedule, you'd naturally sort the slots by start time, then walk through them left to right with one "current block" in hand. Whenever the next slot starts before your current block ends, they overlap — you just stretch the current block's end forward to cover both. The moment a slot starts after your current block's end, that block is finished and printed, and a new block begins. You never have to compare every slot against every other slot — sorting turns "who overlaps with whom" into a single left-to-right sweep.

🚩 Recognition Signal

Reach for merge intervals when you see:

  • The word "overlapping" applied to a list of ranges — "merge all overlapping intervals," "return the intervals after merging any that overlap."
  • "Meetings" or "schedule" framed as a list of [start, end] pairs — "can a person attend all meetings," "minimum number of meeting rooms required," "find free time given everyone's busy intervals."
  • "Insert a new interval into a sorted list of non-overlapping intervals" — a variant where you're not merging a whole unsorted list, but splicing one new range into an already-sorted one, merging only where the new range collides.
  • Any input that is literally an array of two-element [start, end] pairs, with a question about coverage, gaps, overlap count, or a minimal covering set — the shape of the input itself (a list of ranges) is often the biggest tell before you've even parsed the question.

The unifying tell: the data is a collection of ranges, and the question hinges on how those ranges relate to each other along a single axis (usually time or position) — almost always solved by sorting by start time first, then a single linear sweep.

📊 ASCII Diagram

Merging overlapping intervals on a timeline, one sweep after sorting by start:

sorted intervals:  [1,3]  [2,6]  [8,10]  [9,12]  [15,18]

timeline:
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
[--1,3--]
   [-----2,6-----]        <- starts (2) before current end (3) → MERGE → [1,6]
                  [--8,10--]
                     [--9,12--]  <- starts (9) before current end (10) → MERGE → [8,12]
                                          [---15,18---]  <- starts (15) after
                                                             current end (12) → NEW BLOCK

result: [1,6] [8,12] [15,18]

💻 Generic Swift Template

func mergeIntervalsTemplate(_ intervals: [[Int]]) -> [[Int]] {
    guard !intervals.isEmpty else { return [] }

    // 1. Sort by start time — this is what makes a single sweep sufficient.
    let sorted = intervals.sorted { $0[0] < $1[0] }

    var result: [[Int]] = [sorted[0]]

    for interval in sorted.dropFirst() {
        let lastIndex = result.count - 1

        if interval[0] <= result[lastIndex][1] {
            // Overlaps (or touches) the current block — stretch its end.
            result[lastIndex][1] = max(result[lastIndex][1], interval[1])
            // 🔧 Fill in: some problems also want a count, a merged "value", etc.
        } else {
            // No overlap — the current block is finalized, start a new one.
            result.append(interval)
        }
    }

    return result   // 🔧 Fill in: return whatever the problem actually asks for
}

🧩 Worked Example

Merge Intervals — given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

func merge(_ intervals: [[Int]]) -> [[Int]] {
    guard !intervals.isEmpty else { return [] }

    let sorted = intervals.sorted { $0[0] < $1[0] }
    var result: [[Int]] = [sorted[0]]

    for interval in sorted.dropFirst() {
        let lastIndex = result.count - 1
        if interval[0] <= result[lastIndex][1] {
            result[lastIndex][1] = max(result[lastIndex][1], interval[1])
        } else {
            result.append(interval)
        }
    }

    return result
}

// smoke test
print(merge([[1,3],[2,6],[8,10],[15,18]]))   // [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))                  // [[1,5]]
print(merge([[1,4],[0,4]]))                  // [[0,4]]
print(merge([[1,4],[2,3]]))                  // [[1,4]]

This is the template applied with no modifications: sort by start, keep one "current block" (the last element of result), and either stretch its end or open a new block depending on whether the next interval's start falls inside the current block's range. The <= in the overlap check (rather than strict <) is what correctly merges touching intervals like [1,4] and [4,5] into [1,5].

🧸 Memory Sentence

Merge intervals is the conference room sheet — sort the bookings by start time, then sweep once, stretching the current block until a gap forces a new one.

✅ Check Your Understanding

You're given a sorted, non-overlapping list of intervals and a single new interval to insert (not a whole new unsorted list — just one). Why can you solve this in a single linear pass without re-sorting anything, and what three phases does that pass naturally break into relative to the new interval's start and end?

⬅️ Previous: Prefix Sum · Next: Top-K and Heap Pattern ➡️

Clone this wiki locally