Merge Intervals

TL;DR

Sort the intervals by start time, then sweep left to right with a single “current” interval. Each incoming interval either overlaps the current one (extend its end) or doesn’t (emit the current, open a new one). One sort plus one pass — O(n log n) total — solves merge, insert, conflict detection, and peak-concurrency counting. The skeleton barely changes between flavors; only the thing you accumulate does.

If the prompt mentions calendars, bookings, busy times, ranges, or “do these overlap?”, this is almost always the right pattern.

The picture in your head

You have a calendar with a dozen overlapping meetings stacked on top of each other. You want the day to render as a few distinct busy blocks — “9-11 busy, 1-3 busy, 4-6 busy” — instead of a smear of overlapping rectangles. Walk the day from morning to night, keeping a finger on the currently-open block. Each new meeting either extends that block’s right edge or starts a new one once its start passes the current right edge. That finger-sweep is the entire pattern.

The problem it solves

Given n intervals like [[1,3],[2,6],[8,10],[15,18]], decide which ones overlap and return the merged set. The naive answer is “compare every pair.”

def merge_brute(intervals: list[list[int]]) -> list[list[int]]:
    n = len(intervals)
    merged = [False] * n
    out = []
    for i in range(n):
        if merged[i]:
            continue
        s, e = intervals[i]
        for j in range(n):                  # check against every other
            if i == j or merged[j]:
                continue
            s2, e2 = intervals[j]
            if s <= e2 and s2 <= e:         # overlap
                s, e = min(s, s2), max(e, e2)
                merged[j] = True
        out.append([s, e])
    return out

That’s O(n^2) time and only correct after a fixpoint loop in pathological chains ([[1,2],[2,3],[3,4],...]), which can push it toward O(n^3). The problem isn’t the comparison — it’s that you can’t tell whether interval j is “done” without looking at every other interval again.

Sorting fixes that. Once intervals are sorted by start, every later interval has start >= every earlier start, so the only candidate for an overlap is the one currently being built. The two-loop comparison collapses into a single sweep:

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

O(n log n) for the sort, O(n) for the sweep. The sort dominates and the rest is a constant-cost finger walk.

When to reach for it

Signals that merge-intervals is the pattern:

• Input is a list of [start, end] pairs and the question asks about overlap, conflicts, gaps, or coverage.
• The prompt mentions “calendar,” “meeting,” “booking,” “schedule,” “busy,” or “ranges.”
• You need peak concurrency — how many things are active at once.
• You’re given a sorted interval list and asked to splice in a new one.
• The output is itself a list of intervals — you’re producing a coalesced view.

Signals it’s not the pattern: intervals over a graph rather than a number line (interval graph coloring), or weighted intervals with a sum to maximise (weighted interval scheduling — DP, not sweep).

Flavor 1 — merge

Given a list of intervals, merge any that overlap and return the result.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    out = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:          # overlap with current merged
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])     # disjoint → start a new one
    return out

Worked example. intervals = [[1,3],[2,6],[8,10],[15,18]] (already sorted by start).

Three merged intervals out of four inputs. The max(out[-1][1], end) is the detail people miss — without it, [[1,5],[2,3]] would shrink to [[1,3]].

Flavor 2 — insert into a sorted interval list

The list is already sorted and disjoint. You’re handed one new interval and need to slot it in, merging anything it touches. The sweep splits into three phases: intervals strictly before, intervals that overlap, intervals strictly after.

def insert(intervals: list[list[int]], new: list[int]) -> list[list[int]]:
    out, i, n = [], 0, len(intervals)
    # 1. everything ending before new starts → copy as-is
    while i < n and intervals[i][1] < new[0]:
        out.append(intervals[i]); i += 1
    # 2. everything overlapping new → fold into new
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    out.append(new)
    # 3. everything starting after new ends → copy as-is
    while i < n:
        out.append(intervals[i]); i += 1
    return out

Worked example. Insert new = [4,8] into [[1,2],[3,5],[6,7],[8,10],[12,16]].

The folding step is just min on starts and max on ends — same merge logic as flavor 1, just inlined into the new interval.

Flavor 3 — meeting rooms II (count concurrent intervals)

Given meeting times, how many rooms do you need? Equivalent: at the busiest moment, how many intervals are simultaneously active?

Two clean solutions. The first separates starts from ends and runs a two-pointer chronological sweep:

def min_rooms(intervals: list[list[int]]) -> int:
    starts = sorted(s for s, _ in intervals)
    ends   = sorted(e for _, e in intervals)
    rooms = peak = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:    # next event is a start → open a room
            rooms += 1; s += 1
            peak = max(peak, rooms)
        else:                      # next event is an end → free a room
            rooms -= 1; e += 1
    return peak

The min-heap version reads more naturally: keep the earliest end time on top; if a new meeting starts before that, allocate a room, otherwise reuse it.

import heapq
def min_rooms_heap(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    heap = []  # end times of active rooms
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heapreplace(heap, e)   # reuse room
        else:
            heapq.heappush(heap, e)      # need a new one
    return len(heap)

Worked example. intervals = [[0,30],[5,10],[15,20]] using the two-pointer form. After sort: starts = [0,5,15], ends = [10,20,30].

Peak concurrency is 2, so you need 2 rooms. Note step 3: when a start ties an end (starts[s] == ends[e]), the < comparison treats the end as happening first — the room is freed before the new meeting takes it. That’s the right call when intervals are half-open [start, end).

Why it works — the invariant

After sorting by start, sweep left to right. The invariant: the right edge of the current merged interval is the maximum end seen so far among all intervals that have been folded into it. Any new interval [s, e] you encounter has s ≥ every previously-seen start (sort order), so the only question is whether s lands inside the current merged range. If yes, fold; if no, the current range is final — nothing later can extend it leftward, because all later starts are even bigger.

That argument is what licenses the single pass. Without the sort, you’d have to revisit intervals when a smaller start appears later, which kills the linear sweep.

Complexity

• Time: O(n log n) for the sort, O(n) for the sweep. The sort dominates. If the input is already sorted (flavor 2’s “insert into sorted list”), the whole thing is O(n).
• Space: O(n) for the output list. The heap variant of meeting-rooms-II uses O(n) for the heap in the worst case (all intervals overlap). The two-pointer variant uses O(n) for the start/end arrays and is otherwise constant.

Common pitfalls

• Forgetting to sort. The whole pattern collapses without it. If you’re given “sorted by end time,” that’s not the same as sorted by start — sort again by start before sweeping (or rewrite the merge condition).
• Touching intervals — open vs closed. [1,3] and [3,5]: do they overlap? In closed-interval problems (most LeetCode), yes — use start <= end. In half-open [start, end) problems (calendars, meeting rooms), no — use start < end. Pick one, document it, never mix.
• Off-by-one in the heap-based room count. heap[0] <= s vs heap[0] < s: if a meeting ends at exactly the moment the next starts, the same room should be reused — that’s <=. Using < allocates an extra room you don’t need.
• Sorting end times instead of start times. Sorting by end gives you a different algorithm (the greedy for non-overlapping intervals / interval scheduling). It’s the right move there, the wrong move here. Know which problem you’re solving before you pick the sort key.
• Mutating the input. intervals.sort() rearranges the caller’s list. If the caller still needs the original order, copy first (sorted(intervals, key=...)). Forgetting this is a classic interview follow-up question.

Where you see this in production

• Google Calendar conflict detection. When you drag an event and the UI shows “conflicts with 2 events,” it’s literally the meeting-rooms-II count on your day’s intervals — sort by start, sweep, report peak.
• CDN cache range coalescing. HTTP range requests (Range: bytes=0-499, bytes=400-999, …) get merged into the minimal set of underlying fetches. Varnish, NGINX, and Cloudflare’s cache all coalesce overlapping byte ranges using exactly the flavor-1 merge.
• JVM / Go GC region merging. Mark-sweep collectors track free regions as [start, end) extents; after a sweep, adjacent free regions are coalesced with the same template before the next allocation pass.
• Kafka log compaction and segment merging. Compacted topics merge overlapping offset ranges from segment files into a single output segment; the merge step is interval merge over [firstOffset, lastOffset].

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.