Rehearsal room clashes

One rehearsal room, one week, and more requests than the week can hold. The studio manager has to cancel some, and wants to cancel as few as possible.

The problem

Each band submits a booking as a start and an end, both given in minutes since midnight on Monday. A booking occupies the room from its start up to but not including its end, so a band finishing at 600 and a band starting at 600 do not clash — the first is packing up as the second carries gear in.

Two bookings clash if they share any minute. Find the smallest number of bookings the manager must cancel so that no two of the survivors clash. Return the count, not the bookings.

Every request is equally important; the manager has no preference between bands, only a preference for cancelling fewer.

Input. bookings — a list of [start, end] pairs of integers with start < end. The list is in no particular order.

Output. The fewest bookings to cancel.

Example.

bookings = [[540, 600], [570, 630], [630, 690]]   ->  1

The 09:00–10:00 and 09:30–10:30 requests clash, so one of them goes. Cancelling the 09:30 one leaves 09:00–10:00 and 10:30–11:30, which are clear of each other.

A second example, where the greedy choice most people reach for is wrong:

bookings = [[600, 780], [600, 660], [660, 720], [720, 780]]   ->  1

The first request is one long three-hour block; the other three are hour-long and fit back to back inside it. Cancelling the long booking saves three; giving the long booking the room costs three.

Constraints.

• 0 <= len(bookings) <= 10^5
• 0 <= start < end <= 10080 (minutes in a week)
• bookings may repeat exactly

Hints

Approach

Brute force

Try every subset of bookings, check each for clashes, and keep the largest clash-free one. There are 2ⁿ subsets and a check costs O(n log n); at n = 25 that is already 3 × 10⁷ subsets, and the constraints allow 10⁵ bookings.

The insight

Keeping the booking that frees the room earliest is never a mistake, so sort by end time and take everything that still fits.

Suppose some best-possible schedule does not start with the earliest-finishing booking. Swap its first booking for that one: the replacement ends no later, so it cannot collide with anything the schedule kept afterwards, and the schedule is still valid and still the same size. So an earliest-finishing choice is always part of some optimal answer, and the argument repeats on what is left. Sorting by start, or by duration, has no such exchange argument — the second example breaks the first and [[0,10],[9,11],[10,20]] breaks the second.

Algorithm

1. If the list is empty, no cancellations are needed.
2. Sort the bookings by end time.
3. Keep the first; remember free_from, the minute the room is next free.
4. For each remaining booking, if its start is at or after free_from, keep it and move free_from to its end.
5. Otherwise count it as cancelled and leave free_from alone.

Complexity

Time O(n log n) — the sort dominates the single sweep. Space O(n) for the sorted copy, or O(1) extra if you sort the caller's list in place.

Solution

"""Rehearsal room clashes — keep the most bookings by sorting on the end time."""


def solve(bookings):
    if not bookings:
        return 0
    # Sorting by finish time makes the greedy choice safe: the booking that
    # frees the room earliest leaves at least as much room for the rest as any
    # other choice, so keeping it never costs a later booking.
    order = sorted(bookings, key=lambda slot: slot[1])
    cancelled = 0
    free_from = order[0][1]
    for start, end in order[1:]:
        if start >= free_from:      # invariant: free_from is the finish time of
            free_from = end         # the last booking we decided to keep
        else:
            cancelled += 1
    return cancelled

TESTS = [
    (([[540, 600], [570, 630], [630, 690]],), 1),
    (([[600, 780], [600, 660], [660, 720], [720, 780]],), 1),
    (([[540, 600], [600, 660]],), 0),
    (([],), 0),
    (([[480, 1080]],), 0),
    (([[0, 10], [9, 11], [10, 20]],), 1),
    (([[300, 360], [300, 360], [300, 360]],), 2),
]

Pitfalls

• Sorting by start time and keeping greedily hands the room to the long block in the second example and cancels three bookings instead of one.
• Testing start > free_from treats a shared boundary as a clash, so [[540, 600], [600, 660]] reports 1 when the true answer is 0.
• Advancing free_from on a cancelled booking is the subtle one: a booking you rejected must not push the room's free time later, or a long rejected request quietly blocks the short ones behind it.
• Sorting by duration, shortest first, looks plausible and fails on [[0, 10], [9, 11], [10, 20]]: it keeps the middle two-minute booking and cancels both others, for 2 instead of 1.

Variants

• Roadworks calendar — the same sorted intervals, merging one new one in rather than dropping clashes.
• Spectrum licence ledger — intervals that must survive additions and removals over many operations.