Whoever Is Waiting With the Highest Priority
One clerk serves n customers. Customer i arrives at time a[i], needs
d[i] units of service and carries a priority p[i]. Arrival times may come
in any order in the input, and two customers may arrive at the same moment.
The clerk is not trying to be efficient. It follows one rule, written out completely so nothing is left to taste:
the clerk is free at time 0, and after each service at the moment it ended.
when the clerk becomes free:
consider every customer not yet served whose arrival time is <= now.
if that set is empty, the clock JUMPS forward to the smallest arrival
time among the customers not yet served, and the set is taken again.
serve the one with the HIGHEST priority.
ties go to the EARLIER arrival time.
ties again go to the SMALLER input index.
a service is never interrupted once it has started.
Print, in the order the clerk serves them, the index of each customer and the moment their service ended.
``` n = 3, customers (arrival, duration, priority) 0: (0, 5, 1) 1: (0, 3, 9) 2: (0, 4, 5)
all three are waiting at time 0, so priority decides the whole order: customer 1 first, 0 to 3; then customer 2, 3 to 7; then customer 0, 7 to 12 -> 1 3 2 7 0 12 ```
``` n = 4, customers 0: (0, 10, 1) 1: (1, 1, 2) 2: (2, 1, 3) 3: (3, 1, 4)
customer 0 is the only one present at time 0, so it is served even though it has the lowest priority. By the time it ends at 10 all three others are waiting, and priority now runs 4, 3, 2. -> 0 10 3 11 2 12 1 13 ```
## What most people try first
Sorting the customers by priority once and serving that list. That is wrong, and the second worked example is the counterexample: customer 0 has the worst priority and is served first, because at the only moment the clerk was free it was the only customer present. Priority decides between customers who are already waiting, never between a waiting customer and one who has not arrived.
The second instinct is to sort by arrival and walk the list, which is also wrong for the first worked example, where arrival ties nothing at all.
The rule as written is a repeated selection over a set that grows with the clock, so the direct implementation is exactly that:
repeat n times:
best = none
for every unserved i with a[i] <= clock:
keep i if (-p[i], a[i], i) is smaller than the current best key
if best is none:
clock = min arrival over unserved
repeat the scan
clock += d[best]; mark best served; report (best, clock)
## Why the jump is safe
The clock only ever has to jump when nobody is waiting, which means the clerk is idle and no service can start until someone arrives. The earliest such moment is the smallest arrival time among the unserved, and nothing can happen between now and then: no service is running, so no completion can occur, and no arrival can occur before the smallest arrival. So advancing the clock straight to that instant skips only time in which the state cannot change.
After the jump the set of present customers is non-empty, because the customer
whose arrival time was the minimum is now present. The second scan therefore
always finds a best, and the loop runs exactly n times.
## The tie-break is part of the answer
Two customers can share a priority and an arrival time, and the output names an index, so an unpinned tie would make the problem unanswerable. The order is priority descending, then arrival ascending, then index ascending, and the declared test with five identical-priority customers exists to check it.
## Overflow
Durations reach 10^9 and there can be 2000 of them, so the clock can pass
2 * 10^12. Arrival times reach 10^9 as well. Keep the clock in a 64 bit
type. Priorities are compared, never summed, so they cannot overflow.
## Cost
O(n^2) time, which is the cost of the rule read literally, and O(n)
memory.