Intervals: Sort First, Then Sweep

What an interval problem looks like

An interval is just a pair [start, end] — a meeting from 9 to 10, a booking from day 3 to day 7, a segment on a number line. Interval problems ask things like "merge the overlapping ones", "how many rooms do these meetings need", or "remove the fewest so none overlap".

Almost all of them yield to the same first move: sort, then sweep left to right. Unsorted intervals can overlap in any order, and nothing works. Sorted intervals can only interact with their neighbors, and everything becomes one linear pass. The whole skill is picking the right sort key and the right sweep.

The overlap test

Two intervals a and b overlap exactly when:

a.start <= b.end  AND  b.start <= a.end

The easiest way to remember it: figure out when they don't overlap. Either a ends entirely before b starts (a.end < b.start), or b ends before a starts (b.end < a.start). Negate that, and you get the test above.

One thing to settle before writing any code: do touching endpoints count? With the <= test, [1, 3] and [3, 5] overlap (they share the point 3). For meetings, back-to-back usually doesn't count as a conflict, so you would use strict < instead. Read the problem statement and decide deliberately — this single character changes answers.

Sort by start: merging

To merge overlapping intervals into the fewest non-overlapping ones, sort by start time. Then each new interval can only merge with the last merged interval — everything earlier is already sealed off, because starts only increase.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:                     # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)    # extend — with max!
        else:
            merged.append([start, end])
    return merged

Worked example: [[1,3], [2,6], [8,10], [15,18]] is already sorted. [2,6] starts at 2, which is <= 3 (the last end), so merge into [1,6]. [8,10] starts after 6 — new group. [15,18] starts after 10 — new group. Result: [[1,6], [8,10], [15,18]].

Why max() when extending? Because the next interval can be fully contained in the current one. Merge [1,10] with [2,3]: the naive merged[-1][1] = end would shrink the end from 10 down to 3, silently un-merging everything after. max(10, 3) keeps 10. This is the most common merge bug.

Insert Interval is the same idea without a sort (the input is already sorted): copy everything that ends before the new interval starts, absorb everything that overlaps it (tracking min start and max end), then copy the rest. Three clean phases.

Sort by end: keeping the most

A different question: "remove the fewest intervals so that none overlap" (equivalently, keep the most non-overlapping ones). Here sorting by start is the wrong key. Sort by end time and greedily keep every interval that doesn't clash with the last one you kept.

Why earliest end? The interval that finishes first leaves the most room for everything after it. This is the classic exchange argument: take any optimal set of kept intervals and swap its first interval for the earliest-ending compatible one — the count stays the same and the remaining room can only grow. So greedy-by-end is never worse than optimal.

def erase_overlap_count(intervals):
    intervals.sort(key=lambda iv: iv[1])   # sort by END
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:              # compatible: keep it
            kept += 1
            last_end = end
    return len(intervals) - kept           # removals = total - kept

The pairing to memorize: merging → sort by start; keep-the-most / fewest-removals → sort by end.

The event sweep: counting concurrency

"How many meeting rooms do these meetings need?" is really "what is the maximum number of intervals alive at once?" The sweep-line trick: break every interval into two events — +1 at its start, -1 at its end — sort all events by time, and scan with a running counter. The counter's peak is the answer.

Worked example, meetings [[0,30], [5,10], [15,20]]:

Peak is 2 — two rooms. Tie-breaking matters: if a meeting ends at 10 and another starts at 10, process the end before the start (when back-to-back is allowed), otherwise you briefly count a room that is actually free.

The equivalent min-heap formulation: sort meetings by start; keep a heap of end times of meetings currently running. For each new meeting, first pop every end time <= its start (those rooms freed up), then push its end. The heap's maximum size over the run is the room count. The heap version generalizes better — Minimum Interval to Include Each Query uses the same "sweep starts, keep a heap of live candidates" shape, with the heap ordered by interval size instead.

Choosing your tool

Complexity is the same across the board: O(n log n) for the sort, then a linear sweep, with O(n) space at worst. If someone asks where the time goes — it's the sort. The sweep itself is O(n).