When Each Job Finishes
One server handles jobs one at a time. Each job has an arrival time and a duration. The server takes jobs in order of ARRIVAL, and when two arrive at the same instant it takes the one listed EARLIER in the input first. A job runs to completion without interruption.
Print the finishing time of each job, in the order the jobs were given in the input.
``` job 1: arrives 0, takes 3 job 2: arrives 1, takes 2 job 3: arrives 2, takes 1
job 1 runs 0 to 3, finishes 3 job 2 waits, runs 3 to 5, finishes 5 job 3 waits, runs 5 to 6, finishes 6
-> 3 5 6 ```
## The whole simulation is two lines
Sort the jobs by arrival, breaking ties by input position. Then carry a clock:
clock = 0
for each job in that order:
clock = max(clock, arrival) + duration
finish[this job] = clock
The max is the entire idea. If the server is still busy, the job starts when
the server frees up; if the server is idle, it starts when the job arrives. One
expression covers both, and writing it as an if instead is where people
introduce an inequality they then get the wrong way round.
## Two things the statement has to settle, and does
The tie-break. Two jobs arriving at the same instant must have a defined order or the answer is not unique. Here it is input order, and the declared test with two jobs both arriving at 0 pins it.
The output order. Answers are printed in INPUT order, not in the order the jobs ran. That is deliberate: it forces you to carry each job's original index through the sort, which is the part of this problem that actually catches people. Sorting the array and printing the finishing times in sorted order looks right and is wrong whenever the input was not already sorted, which the test with a job arriving at 10 before one arriving at 0 exposes.
## The gap that is not a bug
The server can be IDLE. On arrivals at 0, 5 and 10 with duration 1 each, the finishing times are 1, 6 and 11, not 1, 2, 3. A clock that only ever adds durations and never jumps forward to the next arrival produces the second, which is the other common failure.
## Overflow
Arrival times and durations each reach 10^9, and 2 * 10^5 jobs can queue
behind one another, so the clock reaches about 2 * 10^14. That is far past the
2147483647 a signed 32 bit integer holds, so the clock and the answers need 64
bits. The individual values do not.
## Cost
O(n log n), dominated by the sort; the sweep afterwards is O(n).