A single CPU runs n tasks using round-robin scheduling with a fixed time quantum q. Task i (0-indexed by input order) becomes available at integer time arrival[i] and needs burst[i] units of CPU time to finish. Time advances in whole units.
The ready queue is a FIFO. The scheduling rules are:
min(q, remaining) units (its remaining time may be less than a full quantum).t and it still has work left, any task that arrives at exactly time t is appended to the ready queue before the just-preempted task is appended back. The preempted task then goes to the back of the queue.These rules make the whole simulation deterministic. Report the completion time of every task.
Line 1: two integers n and q separated by a space.
Next n lines: two integers arrival[i] burst[i] for task i, in order i = 0 .. n-1.
A single line with n integers separated by single spaces: the completion time of each task in input order (task 0 first).
Example 1
Input
3 2 0 5 1 3 2 1
Expected
9 8 5
Explanation
With quantum 2: task0 runs 0-2 (rem 3), task1 arrives at 1 and task2 at 2. Order becomes task1,task2,task0. task1 runs 2-4 (rem 1), task2 runs 4-5 and finishes at 5, task0 runs 5-7 (rem 1), task1 runs 7-8 and finishes at 8, task0 runs 8-9 and finishes at 9. Completion times: 9 8 5.
Example 2
Input
2 3 0 4 0 6
Expected
7 10
Explanation
Both arrive at 0 (task0 before task1). task0 runs 0-3 (rem 1), task1 runs 3-6 (rem 3), task0 runs 6-7 and finishes at 7, task1 runs 7-10 and finishes at 10. Completion times: 7 10.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →