The Lowest Numbered Free Till
A shop has c tills, numbered 0 to c - 1. n customers arrive, given in
non-decreasing order of arrival time. Customer i needs d[i] units of
service once a till starts on them.
The discipline is fixed and you are not asked to improve it:
1. customers are served in the order given, strictly. Customer i+1 cannot
start before customer i has started.
2. customer i starts at the later of their own arrival time and the earliest
moment any till is free.
3. if more than one till is free at that moment, the LOWEST numbered one is
used.
For every customer, print the till that served them and the moment their service ended.
``` n = 3, c = 1, customers (0,5) (1,3) (2,4)
one till, so the services form a chain: customer 0 starts at 0 and ends at 5 customer 1 arrived at 1 but the till is busy until 5, so 5 to 8 customer 2 arrived at 2, so 8 to 12 -> 0 5 0 8 0 12 ```
``` n = 3, c = 2, customers (10,1) (10,1) (10,1)
tills 0 and 1 are both free at time 10. The first customer takes till 0 because it is the lower number, the second takes till 1, and the third waits for the earliest free moment, which is 11 on both tills, so it takes till 0 again. -> 0 11 1 11 0 12 ```
## What most people try first
A loop over time, one unit at a time, freeing tills and starting whoever is at
the front. That is a faithful reading of the rules and it is too slow here:
arrival times reach 10^9 and a single service can be 10^9 units long, so
the clock would have to take 10^9 steps that change nothing.
The useful observation is that you never need the clock at all. Keep one number
per till, free[j], the moment till j next becomes available, and process
customers in the order given:
earliest = min over j of free[j]
start = max(arrival[i], earliest)
till = the smallest j with free[j] <= start
free[till] = start + d[i]
## Why the smallest such j always exists
start is at least earliest, and earliest is free[j] for at least one
till j, so that till satisfies free[j] <= start. The scan therefore never
falls off the end, and taking the first j it finds gives exactly the lowest
numbered free till, which is the tie-break the statement names.
The reason it is correct to serve in the given order at all is that arrivals
are non-decreasing. If customer i + 1 could start before customer i, then
at that earlier moment a till was free and customer i had already arrived,
since arrival[i] <= arrival[i+1], so customer i would have taken it.
## The boundary that breaks a careless implementation
Writing free[j] < start instead of free[j] <= start loses the common case
where a till frees at the exact instant the next customer is ready. On the
second worked example that turns 0 12 into no till being found at all.
Two customers may share an arrival time, and c may exceed n, in which case
the later tills are never touched.
## Overflow
With n up to 10^5 and each service up to 10^9, a single till can be busy
until roughly 10^14, which is far outside a signed 32 bit integer. Hold every
time in a 64 bit type. The declared test with three billion-unit services on
one till ends at 3 * 10^9, which already does not fit in 32 bits, and a 32
bit build prints a negative number for it.
## Cost
O(n c) time for the two scans per customer, and O(c) memory.