Interval scheduling

One room, many booking requests, and no two bookings may overlap. Which ones should be accepted to fit in as many as possible? Three natural greedy rules exist, and only one of them is right. This lesson proves it with a second kind of argument, “greedy stays ahead”, and then solves a related problem: how few platforms a station needs.

The most bookings

Each booking is an interval of time: it starts at s and ends at e. We treat it as half-open, as Python slices are: it includes s but not e. So a booking that ends at 5 and one that starts at 5 do not overlap, and both can be accepted. Two bookings overlap when each one starts before the other ends.

The task: choose as many bookings as possible, with no two overlapping. Only the number of bookings counts, not their lengths.

Three rules that look right

Go through the bookings in some order, and accept each one that does not overlap a booking already accepted. In which order?

• Starts first. Fill the room from the beginning of the day.
• Shortest first. Short bookings use up little of the room.
• Ends first. Free the room again as early as possible.

The figure runs all three on the same six bookings. Use the variants to switch between them.

A booking that starts first may run all day and block everything. A short booking may sit across the boundary of two others that fit together. Each wrong rule fails on a small example, which is all it takes to reject it (CORR-4). Ends first gives 4 here, and it is always right.

def most_bookings(bookings):
    # bookings: a list of (start, end) pairs
    count = 0
    # the room is free from here
    free = float("-inf")
    for start, end in sorted(bookings, key=lambda b: b[1]):
        # fits after the last choice
        if start >= free:
            count += 1
            free = end
    return count

Sorting by end costs O(n log n), and the walk is O(n). The variable free is the end of the last accepted booking. Because bookings are taken in order of their end, a new booking overlaps an accepted one exactly when it starts before free, so one comparison checks it against all of them.

Greedy stays ahead

Let the greedy method accept k bookings, g₁, g₂, …, gₖ, in the order it took them, which is also their order in time: g₁ is its first booking, g₂ its second, and so on. Let b₁, b₂, …, bₘ be any best set of m bookings, sorted by time in the same way. We want to show k = m.

Proof by induction on i (CORR-3):

• i = 1. g₁ ends first of all the bookings, so it ends no later than b₁.
• From i to i + 1. bᵢ₊₁ starts no earlier than bᵢ ends, and bᵢ ends no earlier than gᵢ. So bᵢ₊₁ starts no earlier than gᵢ ends: it was still allowed when greedy chose its next booking. Greedy took the allowed booking that ends first, so gᵢ₊₁ ends no later than bᵢ₊₁.

Now suppose the best set had more bookings, m > k. Then bₖ₊₁ starts no earlier than bₖ ends, which is no earlier than when gₖ ends. So bₖ₊₁ fits after greedy’s last booking, and greedy would have accepted it, or some other booking. Greedy stopped at k, so this cannot happen. So k = m.

“Stays ahead” compares the two answers piece by piece and shows that greedy is never behind. An exchange argument works here too: in a best set, replace the booking that ends first with g₁; it ends even earlier, so it overlaps nothing new. Use whichever argument is easier for the problem in front of you.

Fewest platforms

A different question about intervals. Trains arrive and leave at given times; each is in the station from its arrival up to, not including, its departure. Each platform holds one train at a time. How many platforms are needed? Switch the figure to “Platforms”.

A lower bound. Call the largest number of trains in the station at the same moment the depth. Any plan needs at least that many platforms, because those trains each need their own.

The greedy method. Take the trains in order of arrival. Put each on a platform that is already free, if there is one; otherwise open a new platform. It never opens more than the depth: when it opens platform k, the other k − 1 are all busy at that moment, and the new train is there too, so k trains are in at once, and k is at most the depth. The lower bound says no plan can do better, so the greedy method is best.

To find a free platform fast, keep the departure times of the busy platforms in a min-heap (HEAP-4). If the earliest departure is no later than the new arrival, that platform is free: replace its time with the new train’s departure. Otherwise push a new time. At the end the heap holds one time per platform. That is O(n log n) in all.

A second method finds the depth directly. Make a list of events, +1 at each arrival and −1 at each departure, sort them by time, and keep a running count; the largest count is the answer. When a departure and an arrival happen at the same time, the departure must come first, because the platform is free again the moment its train leaves.

Related problems

• Fewest points that hit every interval (for example, the fewest times to check a set of machines while each is running): sort by end, and put a point at the end of each interval that no point has hit yet. The proof is the same as above.
• Covering a stretch with the fewest intervals (cover the time from 0 to T): among the intervals that start no later than the point already covered, take the one that reaches furthest, and repeat.
• Merging overlapping intervals: sort by start, and join each interval to the last merged one while they overlap.
• Bookings with values (the most money, not the most bookings): no greedy rule works. It needs dynamic programming over the bookings sorted by end, with a binary search for the last booking that fits before each one (DYNP, BSRC).