Interval Scheduling and Merging

A calendar full of meetings, a set of overlapping trading windows, or a batch of maintenance outages all share the same underlying object: a list of [start, end] intervals. Three questions come up over and over — how many intervals can you fit without any overlap, what do the intervals look like once overlapping ones are merged into one, and does a new interval conflict with any existing one. All three have an $O(n \log n)$ solution that starts the same way: sort the intervals, but sort by a different field depending on the question.

The idea: sort by the field the question actually depends on

Maximum non-overlapping intervals (interval scheduling): sort by end time. Greedily take the interval with the earliest end time, discard everything that overlaps it, and repeat on what's left. Sorting by end time, not start time, is the whole trick — the earliest-ending interval always belongs to some optimal solution, because finishing earliest leaves the most room for everything after it. This greedy choice is provably optimal, unlike most greedy heuristics.

Merging overlapping intervals: sort by start time. Sweep left to right, keeping a running "current merged interval." If the next interval's start is $\le$ the current merged interval's end, extend the end (merge them); otherwise close the current merged interval and start a new one. One pass after the sort, $O(n)$.

Meeting-room / conflict-checking: same start-time sort, but instead of merging, track how many intervals are simultaneously open with a min-heap of end times — pop any interval that has already ended before the new one starts, otherwise the heap size at any point is the number of concurrent rooms needed.

Worked example: merge [[1,4],[3,6],[5,7],[8,10]]

Already sorted by start. Current merged interval starts as [1,4]. Next is [3,6]: start 3 $\le$ current end 4, so merge — extend end to $\max(4,6)=6$, current becomes [1,6]. Next is [5,7]: start 5 $\le$ current end 6, merge — extend to $\max(6,7)=7$, current becomes [1,7]. Next is [8,10]: start 8 $>$ current end 7, no overlap — close [1,7] as final, start a new current [8,10]. End of list — close [8,10]. Result: [[1,7],[8,10]].

def merge(intervals):                       # O(n log n), sort dominates
    intervals.sort(key=lambda iv: iv[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Where it shows up

Interview staples: merge intervals, non-overlapping intervals, meeting rooms II, insert interval. On a desk, this pattern governs scheduling non-overlapping trading windows around news events or auctions, merging overlapping maintenance or blackout windows across venues into a single unavailability calendar, and computing how many concurrent connections or sessions a system needs to support at peak, which is the meeting-rooms variant with server capacity instead of physical rooms.