Intervals

A small pattern family with a high hit rate: merge, insert, overlap detection, meeting rooms, calendar booking. Almost all of it starts with one decision — what do you sort by?

Merging overlapping intervals

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])           # sort by START
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:               # overlaps the last merged interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

Sort by start, then sweep once. O(n log n), dominated by the sort.

The detail people get wrong: max(merged[-1][1], end). An interval fully contained in the previous one must not shrink it — [1,10] followed by [2,3] stays [1,10].

Whether [1,2] and [2,3] overlap depends on the problem’s convention. Ask. For half-open intervals they don’t; for closed intervals they do. Getting this wrong is a silent off-by-one.

Overlap detection

Two intervals a and b overlap iff:

a.start < b.end and b.start < a.end          # half-open [start, end)
a[0] <= b[1] and b[0] <= a[1]                # closed [start, end]

That two-condition form is much easier to get right than enumerating the four positional cases. Worth memorising.

Non-overlapping intervals — sort by END

The counterintuitive one. “Maximum number of non-overlapping intervals” (activity selection, meeting scheduling) is greedy on the end time.

def max_non_overlapping(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])           # sort by END
    count, last_end = 0, float("-inf")

    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end

    return count

Why end and not start: finishing earliest leaves the most room for everything after it. Picking the earliest-starting interval can grab a very long one that blocks several short ones.

This is the exchange-argument proof of a greedy algorithm, and being able to state it distinguishes understanding from recall. “Minimum intervals to remove to make the rest non-overlapping” is the same algorithm — n - count.

The sweep line

For “how many are active at once” — meeting rooms, peak concurrency, maximum overlap.

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    events = []
    for start, end in intervals:
        events.append((start, 1))                # +1 room
        events.append((end, -1))                 # -1 room

    events.sort(key=lambda x: (x[0], x[1]))      # ties: END before START

    rooms = peak = 0
    for _, delta in events:
        rooms += delta
        peak = max(peak, rooms)

    return peak

The tie-break is the whole trick. At a shared timestamp, process the end (-1) before the start (+1), so a meeting ending at 10:00 frees the room for one starting at 10:00. Sorting (time, delta) gives that for free since -1 < 1.

Get the tie-break backwards and you over-count rooms by one whenever meetings abut. That’s the bug an interviewer is watching for.

The heap alternative — push end times, pop those that have passed — is equivalent and slightly more code.

Insert into a sorted list

def insert(intervals: list[list[int]], new: list[int]) -> list[list[int]]:
    out, i, n = [], 0, len(intervals)

    while i < n and intervals[i][1] < new[0]:    # entirely before
        out.append(intervals[i]); i += 1

    while i < n and intervals[i][0] <= new[1]:   # overlapping - absorb
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    out.append(new)

    out.extend(intervals[i:])                    # entirely after
    return out

Three phases: before, overlapping, after. O(n) with no sort, since the input is already sorted.

Choosing the sort key

The summary that resolves most interval problems:

Interview angle

• “How do you merge overlapping intervals?” — sort by start, then sweep, extending the last merged interval when the next one starts before it ends. Use max on the end so a fully contained interval doesn’t shrink it.
• “Maximum non-overlapping intervals — why sort by end?” — finishing earliest leaves the most room for what follows. Sorting by start can pick a long interval that blocks several shorter ones. It’s the standard greedy exchange argument.
• “Minimum meeting rooms?” — a sweep line: +1 at each start, -1 at each end, sort by time, and track the running peak. The critical detail is processing ends before starts at equal timestamps, or you over-count when meetings abut.
• “How do you test whether two intervals overlap?” — a.start < b.end and b.start < a.end for half-open. Far easier to get right than enumerating positional cases — and confirm the convention, because closed intervals need <=.
• “What’s the complexity?” — O(n log n) for anything requiring a sort, O(n) if the input is already sorted, as in the insert case.