Lane bookings

A council pool takes lane reservations over the counter and never turns one away. After each one the duty manager needs a single number: how many lanes must be roped off to honour everything booked so far.

The problem

A reservation is a start minute and an end minute, counted from opening time. A swimmer holds a lane for [start, end) — they are out of the water at end, so a reservation ending at minute 14 and one starting at 14 can share a lane.

Reservations arrive one at a time and are all accepted. After each one, report the largest number of reservations in the water at the same instant, anywhere in the timetable so far. That count is the number of lanes needed; it never decreases, and it rises by at most one per reservation.

Input. bookings — a list of [start, end] pairs of integers in arrival order, with start < end. The list may be empty.

Output. A list of integers of the same length: the lane count required after each reservation is added.

Example.

bookings = [[8, 14], [40, 52], [8, 25], [12, 20], [10, 30], [46, 60]]
  ->  [1, 1, 2, 3, 4, 4]

The second reservation is far from the first, so one lane still serves. The third overlaps the first, the fourth puts three swimmers at minute 12, and the fifth makes minutes 12 to 14 hold four. The last overlaps only [40, 52], which needs two lanes, so the answer stays at 4.

A second example, where reservations meet end to end:

bookings = [[6, 9], [9, 12], [7, 11], [8, 10]]   ->  [1, 1, 2, 3]

[6, 9] and [9, 12] share a lane, since the first swimmer is out at minute 9. Then [7, 11] crosses both, and [8, 10] makes minute 8 to 9 hold three.

Constraints.

• 0 <= len(bookings) <= 400
• 0 <= start < end <= 10^6

Hints

Approach

Brute force

After every reservation, test every pair for overlap and check which groups share an instant. That is O(n²) per reservation, O(n³) over the day, and it does not even answer the question: three reservations can overlap pairwise while no instant holds all three.

The insight

A reservation is two marks on a timeline — plus one at its start, minus one at its end — and the swimmers in the water at an instant is the running total of every mark at or before it, so the lane count is the largest running total.

Keying the marks by minute makes the half-open rule fall out for free: a departure and an arrival at minute 9 land on the same key and sum to zero, so the total never bulges there. That removes the tie-break question rather than answering it. Only marked minutes matter, since the total is flat between them.

Algorithm

1. Keep a map from minute to net change, plus the marked minutes in sorted order.
2. For each reservation, add one to the change at start and subtract one at end, inserting either minute into the sorted list if it is new.
3. Sweep the marked minutes in order, accumulating changes and tracking the largest running total.
4. Append that maximum and move to the next reservation.

Complexity

Time O(n²) — each of the n reservations does one sweep of at most 2n marked minutes, with the insertion into the sorted list costing the same shift. Space O(n) for the timeline.

If minutes are bounded — a pool day is 1440 of them — the map becomes a plain array of that length, and one prefix-sum pass answers the whole batch in O(n + T) whenever the running answers are not needed. That is the counting form of the same idea: address the timeline instead of sorting it.

Solution

"""Lane bookings — plus-one/minus-one marks on a sorted timeline, swept each time."""

from bisect import insort


def solve(bookings):
    change = {}     # minute -> net change in swimmers at that minute
    marked = []     # the same minutes, kept sorted
    answers = []

    for start, end in bookings:
        for minute, delta in ((start, 1), (end, -1)):
            if minute not in change:
                insort(marked, minute)
                change[minute] = 0
            change[minute] += delta

        # invariant: after summing every mark up to `minute`, `live` is the
        # number of swimmers in the water there, and the count is flat between
        # marked minutes, so the peak is seen at one of them.
        live = peak = 0
        for minute in marked:
            live += change[minute]
            if live > peak:
                peak = live
        answers.append(peak)

    return answers

TESTS = [
    (([[8, 14], [40, 52], [8, 25], [12, 20], [10, 30], [46, 60]],), [1, 1, 2, 3, 4, 4]),
    (([[6, 9], [9, 12], [7, 11], [8, 10]],), [1, 1, 2, 3]),
    (([],), []),
    (([[0, 1000000]],), [1]),
    (([[50, 60], [50, 60], [0, 100]],), [1, 2, 3]),
    (([[5, 10], [10, 15], [15, 20], [20, 25]],), [1, 1, 1, 1]),
]

Pitfalls

• Marking the end minute as occupied. Subtracting at end + 1 instead of end turns [[6, 9], [9, 12]] into two lanes, because minute 9 is counted as holding both swimmers.
• Reading the count only at the new reservation's start. With [[50, 60], [50, 60]] booked, a new [0, 100] sees one swimmer at minute 0 and reports 2, when minute 50 now holds 3.
• Keeping the marks as a list of events sorted by minute alone. A plus one and a minus one at the same minute then land in arbitrary order, and the plus going first invents an overlap that lasts no time. A map keyed by minute makes that order unrepresentable.

Variants

• Kiln slots — the same peak count, asked once over a fixed list instead of after every insertion.
• Irrigation windows — the same timeline, merged into runs rather than counted.