2158. Round Robin With a Fixed Quantum

One server runs n jobs under round robin with quantum q. Job i arrives at time a[i] and needs d[i] units of work in total. Work can be split: a job may run, be set aside, and run again later.

The discipline, with the one ordering question that matters settled explicitly:

there is a single queue. The server always runs the job at its front. a job runs for min(q, work remaining). Then: first, every job whose arrival time is <= the new clock joins the BACK of the queue, in order of arrival and then of index then, if the job still has work left, IT joins the back, behind those arrivals if it has no work left, it departs and its finish time is the new clock if the queue is empty and jobs remain, the clock jumps to the next arrival.

Print one line per job in the order the jobs finish.

``` n = 3, q = 2, jobs (0,5) (0,3) (0,4)

queue 0 1 2. 0 runs 0-2 (3 left), 1 runs 2-4 (1 left), 2 runs 4-6 (2 left), 0 runs 6-8 (1 left), 1 runs 8-9 and FINISHES, 2 runs 9-11 and FINISHES, 0 runs 11-12 and FINISHES -> 1 9 2 11 0 12 ```

``` n = 2, q = 1, jobs (0,2) (1,1)

job 0 runs 0-1 and has 1 left. The clock is now 1, so job 1 arrives and joins the queue BEFORE job 0 is put back. Queue is 1 then 0. job 1 runs 1-2 and FINISHES, job 0 runs 2-3 and FINISHES. -> 1 2 0 3 ```

## What most people try first

A queue, a quantum, and the preempted job pushed back before the new arrivals are admitted. It is one line different from the rule above and it gives a different answer on the second worked example: it produces 0 2 then 1 3 instead. That is why the admission order is written into the statement rather than left as an implementation detail.

The other common first attempt is to step the clock one unit at a time, which is correct but spends a steps doing nothing when the first arrival is at 10^9. Advance the clock by a whole slice instead.

## Why the finishing order is well defined

At every moment the server is running at most one job, and a job departs only at the instant its remaining work hits zero. Two jobs can therefore never depart at the same moment, because the departure of the running job is the only event that can end a slice at that instant and only one job is running. So the output order is total and no tie-break is needed for it.

The queue itself needs a tie-break, and the statement gives it: simultaneous arrivals enter in index order, and a preempted job enters behind every arrival admitted at the same clock value.

## Termination

Each slice removes min(q, remaining) units of work from the total, which is at least 1 because every duration is at least 1 and q is at least 1. The total work is finite, so the number of slices is at most the sum of all durations and the loop ends. When the queue empties with jobs still unarrived, the clock jump makes progress because the next arrival time is strictly greater than the current clock.

## Overflow

The sum of all durations is at most 10^6 and an arrival is at most 10^9, so the clock never passes about 1.001 * 10^9. That fits in a signed 32 bit integer, since INT_MAX is 2147483647. No test here overflows a 32 bit build, and none is tagged as if it did. The reference solutions still use 64 bit times, which costs nothing and removes the question.

## Cost

O(total work / q + n) slices, each O(1) amortised, and O(n + slices) memory if the queue is an array with a head index.

Constraints - `1 ≤ n ≤ 1000` - `1 ≤ q ≤ 10^9` - `0 ≤ arrival ≤ 10^9` - `1 ≤ work ≤ 1000`, and the sum of all work is at most `10^6` - simultaneous arrivals enter the queue in index order - a preempted job enters the queue behind every job admitted at the same clock value