The Clerk Who Serves the Newest Arrival
One clerk serves n customers. Customer i arrives at a[i] and needs d[i]
units of service. Arrival times may appear in any order in the input and two
customers may share one.
This clerk works through the pile from the top:
the clerk is free at time 0, and again at the end of each service.
when the clerk becomes free:
consider every customer not yet served whose arrival is <= now.
if none, the clock jumps to the smallest arrival among the unserved.
serve the one who arrived LATEST. Ties go to the LARGER input index.
no service is ever interrupted.
Print, in service order, the index of each customer and the moment their service ended.
``` n = 3, customers (0,5) (1,3) (2,4)
only customer 0 is present at time 0, so it is served, 0 to 5. at time 5 both 1 and 2 are waiting; customer 2 arrived later, so it goes next, 5 to 9, and customer 1 last, 9 to 12. -> 0 5 2 9 1 12 ```
``` n = 3, customers (0,2) (0,2) (0,2)
all three arrive together, so the arrival time ties and the larger index wins: 2, then 1, then 0. -> 2 2 1 4 0 6 ```
## What most people try first
Sorting by arrival time descending and serving that order. It is wrong for the same reason the opposite mistake is wrong on a priority queue: the rule picks the latest arrival among those who are PRESENT, and a customer who has not arrived yet is not present. In the first worked example, customer 2 arrives latest of all three, and yet customer 0 is served first, because at time 0 it was the only one there.
The direct reading is a selection loop:
repeat n times:
best = the unserved customer with a[i] <= clock maximising (a[i], i)
if there is none, clock = min arrival over unserved, then choose again
clock += d[best]; report (best, clock)
## Why this is a stack, and why that matters
Push the customers onto a stack in order of (arrival, index) as the clock
passes their arrival times, and the rule becomes "pop the top". The latest
arrival with the largest index on a tie is exactly the most recently pushed
item, so last in, first out is not an analogy here, it is the definition. That
is also the second implementation used to verify every declared output, written
differently on purpose so that a mistake in the scanning version cannot be
mirrored in the checker.
The consequence worth noticing is starvation: an early customer can wait arbitrarily long, and in the second worked example customer 0 is served last despite arriving first. Nothing in the rule prevents that, and the problem does not ask you to fix it.
## The clock jump is necessary
If nobody is present the clerk is idle, no service is running, and no arrival
can happen before the smallest unserved arrival time. So nothing can change
between now and then and the clock may move straight there. Stepping it one
unit at a time is correct and far too slow, since arrival times reach 10^9.
## Overflow
Up to 2000 services of 10^9 each, starting from an arrival of up to 10^9,
put the clock as high as about 2 * 10^12. A signed 32 bit integer stops at
2147483647, so the clock must be 64 bit.
## Cost
O(n^2) with the scanning version above, or O(n log n) with the stack and a
sort, and O(n) memory either way.