Earliest Start, or Walk Out
Two tills work at different speeds. Till 0 takes s0 units of time per unit of
work and till 1 takes s1, so a customer with d units of work occupies till
j for d * sj units of time once started.
n customers arrive in non-decreasing order of arrival time. Customer i
brings d[i] units of work and will wait at most p[i] units of time before
giving up.
when customer i arrives:
for each till j, start[j] = max(arrival[i], the moment till j is free)
pick the till with the SMALLER start, and till 0 on a tie.
this comparison looks only at the start times. It does NOT consider
the speeds.
if the chosen start is more than p[i] later than the arrival, the
customer LEAVES. No till is touched and nothing else changes.
otherwise the customer occupies that till from the chosen start until
the chosen start plus d[i] * sj.
Print two integers: how many customers left, and the moment the last service
ended, or 0 if nobody was served.
``` s0 = 1, s1 = 1, customers (0,5,0) (0,3,0) (0,4,0)
customer 0 has start 0 on both tills, the tie gives till 0, busy to 5. customer 1 has start 5 on till 0 and 0 on till 1, so till 1, busy to 3. customer 2 has start 5 and 3, so till 1, but 3 is 3 later than its arrival and its patience is 0, so it leaves. -> 1 5 ```
``` s0 = 1000, s1 = 1, customers (0,1000000,0) (0,1000000,0) (0,1000000,0)
customer 0 ties at start 0 and takes the SLOW till 0, busy to 10^9. customer 1 has start 10^9 on till 0 and 0 on till 1, so till 1, busy to 10^6. customer 2 has start 10^9 and 10^6, so the earliest is 10^6 on till 1, which is 10^6 later than its arrival. Its patience is 0, so it leaves. -> 1 1000000000 ```
## What most people try first
Choosing the till that will finish the customer soonest, which means comparing
start[j] + d * sj rather than start[j]. That is the sensible rule and it is
not the one written down. The second worked example exists to separate them: a
customer who can start immediately on the slow till does so, and the fast till
sits idle, which is exactly why one customer later walks out.
Modelling the speeds is the whole reason that distinction can be seen at all.
With s0 = s1 the two rules agree on every input, so a problem without speeds
would not be able to tell a correct solution from this particular wrong one.
## Why the patience test is where it is
Patience is compared against the WAIT, start - arrival, and not against the
start or the departure. A customer who waits exactly p[i] stays, since the
rule says "more than", so the comparison is start - arrival > p[i].
The test happens after the till is chosen and before anything is written. That ordering matters: a customer who leaves must leave no trace, so the chosen till's free time is unchanged and the next customer sees the shop exactly as it was. A solution that assigns first and un-assigns afterwards has to restore the free time exactly, and since the free time it overwrote is the one it needs back, that is a bug waiting to happen.
## Why one pass suffices
Arrivals are non-decreasing and a customer's fate depends only on the two free times at the moment they arrive. Those free times are determined entirely by the customers already processed, because a customer who left changed nothing and a customer who was served fixed one free time once and for all. So a single left to right pass holding two numbers is correct, and the declared outputs here are cross-checked against a version that rebuilds both free times from scratch at every arrival.
## Overflow
One service can be 10^6 units of work on a till of speed 1000, which is
10^9 units of time. With 2000 customers chaining on one till the free time can
reach about 2 * 10^12, and arrivals add another 10^9. A signed 32 bit
integer stops at 2147483647, so the free times, the starts and the answer all
have to be 64 bit. The product d[i] * sj alone reaches 10^9, which still
fits in 32 bits, so a build that is only careless about the product and not
about the sums can pass the small tests and fail the long chains.
## Cost
O(n) time and O(1) memory beyond the input.