Intervals: sort by start, then look back once

A team's shared calendar holds the day's bookings: 9–11, 10–12 and 14–15. Two questions keep coming up. When is somebody busy? 9–11 and 10–12 run into each other, so the busy times are 9–12 and 14–15. And how many meeting rooms do the bookings need, if a room holds one meeting at a time?

Each booking is an interval: a start and an end. Comparing every pair to find the clashes takes n(n − 1)/2 comparisons, about 50 million for 10,000 bookings. Both have a faster answer that starts the same way: sort the intervals by start, in O(n log n) with merge sort. Then one pass merges the busy times, and one pass with a heap counts the rooms.

interval

A start and an end, written [s, e] or s–e, with the start before the end. The visualisers letter them A, B, C… in input order.

overlap

Two intervals overlap when each starts before the other ends. Whether two that only touch, like [1, 4] and [4, 5], count as overlapping is each problem's choice.

nested

One interval lies inside another: it starts no earlier and ends no later, like [2, 3] inside [1, 5].

sweep

One pass over the intervals in order of start, carrying a little state: the current merged interval, or the time each room becomes free.

min-heap of end times

A heap holding, for each room opened so far, the time it is next free, with the earliest on top: the room that frees up first.

Merge Intervals turns every group of overlapping intervals into one. Here intervals that touch count as overlapping: [1, 4] and [4, 5] leave no gap between them.

Why is one look back enough? The merged intervals come out in order and apart, each ending before the one after it begins. The interval being checked starts no earlier than the last merged one, which began after every earlier one had ended, so the last is the only one it can reach. And once an interval starts after the last merged end, that merged interval is final: everything still to come starts later too.

The second question is meeting rooms: the fewest rooms that hold every meeting, never two at once in one room. Activity selection in greedy algorithms asked the reverse: with one room, keep the most meetings, by earliest finish. Here every meeting is held: meetings get rooms in order of start, and a min-heap holds each room's end time. A room is free again the moment its meeting ends.

Only the top of the heap matters: if the room that frees up first is still busy, every room is. And a room opens only when every room's meeting has started and not yet ended, so at that moment one more meeting than there are rooms is running. The rooms never outnumber the most meetings running at once, and no schedule can use fewer: each of those meetings needs its own room.

Seven unsorted intervals. After the sort, the first opens the merged list; before each of the other six, predict whether it extends the last merged interval, lies inside it, or starts a new one. Touching counts as overlapping.

Seven intervals became two, [1, 6] and [8, 16]. F lay inside [1, 4] and C inside [8, 14], and E only touched [8, 14] at 14, which was enough to join it.

Here is the merge as a function, on intervals already sorted by start. merged starts with a copy of the first interval, so the input never changes. last is a second name for the last merged interval, not a copy, so writing last[1] changes the interval inside merged: two arrows point at the same list.

def merge(spans):
    merged = [[spans[0][0], spans[0][1]]]
    for start, end in spans[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

spans = [[1, 5], [2, 3], [4, 8], [10, 12]]
result = merge(spans)
text = ''
for start, end in result:
    text += '[' + str(start) + ', ' + str(end) + '] '
print(text.strip())

[2, 3] is the case that catches people out: it starts after [1, 5] but ends earlier. Here one interval contains all the others.

Rooms have a rule about touching too: Meeting Rooms reuses a room whose end time is no later than the next start.

The last trap mixes the two questions up. Merging says when someone is busy, not how many rooms that takes:

• Two intervals overlap when each starts before the other ends; whether touching counts is the problem's choice, one character in the code.
• Sorted by start, an interval can only overlap the last merged one, so merging is one pass: extend the end to max(last.end, x.end), not x.end, since a nested interval ends earlier; or start a new interval. O(n log n), for the sort.
• Meeting rooms: in start order, reuse the top of a min-heap of end times if that room is free by the next start, and open one otherwise. O(n log n). The rooms are the most meetings running at once, not the size of a merged block.
• Next: greedy algorithms, where sorting by finish keeps the most intervals in one room. Practise with Merge Overlapping Intervals, Insert a Range into a Sorted List and Fewest Meeting Rooms, or open the merge intervals and meeting rooms visualisers.