The Waiting Room That Fills Up
A shop has c tills, numbered from 0, and a waiting room that holds at most
cap people. n customers arrive in non-decreasing order of arrival time, and
customer i needs d[i] units of service.
Everything that could be ambiguous is settled here:
a customer who finds a till free at the instant they arrive starts at once,
on the LOWEST numbered free till.
otherwise, if fewer than cap people are already waiting, they sit down at the
back of the waiting room.
otherwise they are turned away, leave, and never come back.
a WAITING customer starts the instant a till becomes free, which is usually
earlier than the next arrival. The person at the front of the waiting room
goes first, onto the till that freed. If two tills free at the same instant,
the lowest numbered one is used.
Print two integers: how many customers were turned away, and the moment the
last service of the day ended. If no customer is ever served, print 0 for
that second number.
``` n = 3, c = 1, cap = 0, customers (0,5) (1,3) (2,4)
customer 0 takes the only till, 0 to 5. Customers 1 and 2 arrive while it is busy and there is nowhere to wait, so both are turned away. -> 2 5 ```
``` n = 3, c = 1, cap = 1, customers (0,5) (1,3) (2,4)
customer 0 takes the till, 0 to 5. Customer 1 sits down. Customer 2 arrives at 2 and the one seat is taken, so it is turned away. At time 5 the till frees and customer 1 starts, 5 to 8. -> 1 8 ```
## What most people try first
Deciding everything at arrival instants only. That is the natural reading, and it is wrong, because the waiting room empties at moments when nobody arrives. If the till frees at 5 and the next arrival is at 100, the waiting customer starts at 5, not at 100. A solution that only looks at arrivals reports a last departure that is too late and, worse, finds the waiting room still full when a later customer arrives, so it turns away people who should have been seated.
So the loop has to handle two kinds of event in a fixed order. Processing arrivals in the order given, and before each one:
while someone is waiting and the earliest till frees at or before this arrival:
that till takes the front of the waiting room, starting when it freed
and only then consider the arriving customer against the three cases above. After the last arrival, the waiting room drains the same way.
## Why the two stages cannot be merged
The arriving customer's own test is "is a till free at my arrival time", and that question has a different answer depending on whether the waiting room has already been served. Draining first is what the rule describes, because the waiting customer's start time is strictly earlier than the arrival, and earlier events always happen first. Merging the stages, or doing them the other way round, lets a newcomer take a till that a waiting customer had already claimed, which is queue-jumping the statement forbids.
The drain loop terminates because each pass removes one person from the waiting room and never adds one, and the room is finite.
## The boundaries that are easy to miss
cap may be 0, which means nobody ever waits: a customer either starts at once
or is turned away. The first worked example is that case.
The free test is free[j] <= arrival, not <. A till that frees at the exact
instant of an arrival is free for that customer.
A turned-away customer changes nothing at all. It does not occupy a till, a seat, or a moment of time.
## Overflow
Up to 2000 customers of 10^9 each can chain onto one till, so a departure can
reach about 2 * 10^12, which is well outside a signed 32 bit integer. Keep
every time in a 64 bit type. The count of turned-away customers is at most
n, so it is small.
## Cost
O(n c + n) time, since each customer triggers at most a few scans over the
c tills, and O(c + cap) memory.