Merge Intervals

Before we start

Intervals feel different from array-value problems — you're dealing with ranges instead of single numbers. But the core pattern is beautifully simple. By the end you will be able to:

• See overlapping intervals as overlapping events on a timeline.
• Explain why sorting by start time and a single pass is all you need.
• Apply the pattern to merging, inserting, and counting intervals.

Stop at every Pause & Think box.

Picture this first (no code yet)

10:00–11:30,   9:00–10:15,   12:00–13:00,   10:45–12:30

 9:00        10:00       11:00       12:00       13:00
  |            |           |           |           |
  [===9:00–10:15===]
               [======10:00–11:30======]
                         [=====10:45–12:30=====]
                                     [===12:00–13:00===]

The actual problem

Given a list of intervals [start, end], merge all overlapping intervals and return the result.

input  = [[1,3], [2,6], [8,10], [15,18]]
output = [[1,6], [8,10], [15,18]]

explanation:
  [1,3] and [2,6] overlap (2 ≤ 3) → merged into [1,6]
  [8,10] has no overlap
  [15,18] has no overlap

First, the slow way (so you feel the pain)

Naive approach: For every interval, check every other interval to see if they overlap. If so, merge and repeat until nothing changes.

# Pairwise comparison — keeps looping until stable
def merge_naive(intervals):
    changed = True
    while changed:
        changed = False
        result = []
        used = [False] * len(intervals)
        for i in range(len(intervals)):
            if used[i]: continue
            cur = intervals[i]
            for j in range(i+1, len(intervals)):
                if used[j]: continue
                if cur[0] <= intervals[j][1] and intervals[j][0] <= cur[1]:
                    cur = [min(cur[0], intervals[j][0]),
                           max(cur[1], intervals[j][1])]
                    used[j] = True
                    changed = True
            result.append(cur)
        intervals = result
    return intervals

Count the horror:

n = 10        →  up to 100 pair comparisons, multiple passes
n = 10,000    →  up to 100,000,000 comparisons per pass

The clean solution does it in a single pass after one sort — O(n log n) total, dominated by the sort. The merge pass itself is O(n).

The turning point

Two intervals [a, b] and [c, d] (where a ≤ c because we sorted) overlap if and only if c ≤ b — the second one starts before the first one ends. When they overlap, the merged interval is [a, max(b, d)] — same start, the later end.

When there's no overlap (c > b), the current interval is done — it can never grow again (because everything to the right starts even later). Push it to the result and start fresh with [c, d].

The sorting step is the whole key. Without it, an interval that should merge might be anywhere in the list. With it, all intervals that could possibly merge with the current one are adjacent in the sorted order — you see them one by one, in sequence, and never have to look back.

The one idea to remember

Watch it happen, frame by frame

Input after sorting by start: [[1,3], [2,6], [8,10], [15,18]]

Start: current = [1, 3], result = []

Step 1: next = [2, 6]
  Does 2 ≤ 3?  YES → overlap.  Extend: current = [1, max(3,6)] = [1, 6]

Step 2: next = [8, 10]
  Does 8 ≤ 6?  NO → gap.  Push [1,6] to result. current = [8, 10]
  result = [[1, 6]]

Step 3: next = [15, 18]
  Does 15 ≤ 10?  NO → gap.  Push [8,10] to result. current = [15, 18]
  result = [[1, 6], [8, 10]]

End of array: Push final current = [15, 18]
result = [[1, 6], [8, 10], [15, 18]]  ✅

Sorted: [[1,4],[2,6],[3,5],[7,9]]

current = [1,4]
next=[2,6]: 2≤4 → extend to [1, max(4,6)]=[1,6]
next=[3,5]: 3≤6 → extend to [1, max(6,5)]=[1,6]  (no change, 5 < 6)
next=[7,9]: 7≤6? NO → push [1,6]. current=[7,9]
End → push [7,9]

result = [[1,6],[7,9]]  ✅

Now, the code — line by line

def merge(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])    # sort by start time

    result = [intervals[0]]                # seed with the first interval

    for start, end in intervals[1:]:       # sweep from second onward
        last_end = result[-1][1]           # end of the interval we're currently extending

        if start <= last_end:              # overlap: this interval starts inside the current one
            result[-1][1] = max(last_end, end)   # extend the end (might be swallowed)
        else:                              # gap: current interval is final
            result.append([start, end])   # start a new block

    return result

Line by line with the calendar story:

• intervals.sort(...) — sort all meetings by start time, so overlapping ones are adjacent.
• result = [intervals[0]] — the first meeting is always the start of some block.
• for start, end in intervals[1:] — walk through remaining meetings one by one.
• last_end = result[-1][1] — the end of the meeting block we're currently in.
• if start <= last_end: — new meeting starts before current block ends → they overlap.
• result[-1][1] = max(last_end, end) — extend the block to the later endpoint. Use max because the new meeting might end earlier (completely inside the current block).
• else: result.append(...) — clear gap; the current block is sealed, start a fresh one.

Why does it work?

After sorting by start, the array has a beautiful property: if interval i doesn't overlap with j (where i comes before j), then i doesn't overlap with any interval after j either (they all start even later). So when we declare the current interval "done" and move on, we know with certainty it will never be extended again.

max(last_end, end) handles the case where a later interval is completely contained inside the current one:

current: [1, 10]
next:    [3, 6]    → completely inside
max(10, 6) = 10    → current stays [1, 10], correctly unchanged

Why is it so fast?

The sort is O(n log n). The sweep is a single for-loop — exactly n-1 iterations, O(n). The sort dominates.

n = 100,000   →  ~1,700,000 operations (sort) + 100,000 (sweep)

When should I reach for this? (the trigger list)

• Problem involves intervals, ranges, or time slots.
• You need to find overlapping, non-overlapping, or covering ranges.
• Keywords: "merge intervals," "meeting rooms," "free time," "overlap."
• Brute force would require pairwise comparison — O(n²).
• The key smell: after sorting by start, overlaps become adjacent.

The same trick in three disguises

Disguise 1 — Merge Intervals (LC #56)

The pattern itself. Sort by start, sweep and extend or push.

Disguise 2 — Insert Interval (LC #57)

Given a list of already-merged (non-overlapping) intervals and a new interval, insert it and re-merge. Three phases:

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

    # Phase 1: add all intervals that end before newInterval starts (no overlap)
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Phase 2: merge all overlapping intervals into newInterval
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)

    # Phase 3: add all intervals that start after newInterval ends (no overlap)
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Same overlap condition (start ≤ end), same max extension. Three explicit phases instead of one loop.

Disguise 3 — Meeting Rooms (LC #252)

Can a person attend all meetings? Simply check if any two consecutive meetings (sorted by start) overlap:

def canAttendMeetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:   # overlap
            return False
    return True

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = []                              # stores end times of active meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)   # recycle a room that's freed up
        else:
            heapq.heappush(heap, end)      # need a new room
    return len(heap)

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll sort the intervals by start time, then do a single sweep. I keep track of the interval I'm currently extending. For each next interval, if it starts before the current one ends, they overlap — I extend the end to the maximum of the two. Otherwise there's a gap — I push the current to results and start fresh. O(n log n) for the sort, O(n) for the sweep."

Check yourself

Practice problems

When you can solve LC #56 from memory and explain why max(last_end, end) is needed, you've learned this pattern.

Next up: Interval Scheduling — instead of merging intervals, we greedily select the maximum number that fit without overlapping.