Round Robin Completion Times
A single processor runs tasks round-robin with a time slice of quantum. Task i arrives at time arrival[i] and needs work[i] units of processor time. arrival is sorted from earliest to latest, and several tasks may arrive at the same time.
- Waiting tasks sit in a ready queue. A task joins the back of the queue when it arrives; tasks arriving at the same time join in index order.
- The processor takes the task at the front of the queue and runs it for
quantumunits, or for its remaining work if that is less, without interruption. - When that run ends, first every task that has arrived by then (arrival time less than or equal to the current time) joins the back of the queue, and only after that does the task that just ran rejoin the back of the queue, if it still has work left.
- If the queue is empty, the processor waits until the next task arrives.
Return a list where item i is the time at which task i finishes its work.
Example 1
arrival [0,0,0]
work [3,1,2]
quantum 2
returns [6,3,5]
Task 0 runs 2 units (time 2) and rejoins behind tasks 1 and 2. Task 1 finishes at 3, task 2 at 5, and task 0 runs its last unit until 6.
Example 2
arrival [0,2]
work [4,2]
quantum 2
returns [6,4]
Task 0 runs until time 2. Task 1 arrives exactly then, so it joins the queue before task 0 rejoins: task 1 finishes at 4, then task 0 at 6.
Constraints
1 <= len(arrival) == len(work) <= 200 <= arrival[i] <= 100, sorted in non-decreasing order1 <= work[i] <= 201 <= quantum <= 10
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.