TopCoder problem "RRSchedule" used in TCHS SRM 52 (Division I Level Two)

Problem Statement

When multiple tasks are executed on a single CPU, they are not truly run in parallel. Instead, the CPU spends some time on each task in turn, and a scheduler is used to decide which task to run at any given time. Real-world schedulers are quite complex and must try to balance conflicting priorities.

For the purposes of this problem, we will consider only a simple "round-robin" scheduler. There are N tasks, numbered 0 to N-1. The scheduler runs each task in turn for one second, starting with task 0 and proceeding with tasks 1, 2, ..., N-1, before starting again at 0. Once a task completes executing, the scheduler will skip over that task in future.

Element i of tasks is the number of seconds of execution time required by task i. Return N integers, the ith of which is the total time the system has been running when task i completes.

Definition

Class:	RRSchedule
Method:	terminalTimes
Parameters:	int[]
Returns:	int[]
Method signature:	int[] terminalTimes(int[] tasks)
(be sure your method is public)

Constraints

tasks will contain between 1 and 50 elements, inclusive.

Every element of tasks will be between 1 and 20,000,000, inclusive.

Examples

{2, 1, 2, 4}

Returns: {5, 2, 6, 9 }

For the first four seconds, each task gets one turn, and the 2nd task completes after 2 seconds. The next two seconds complete the first and third tasks, and three more seconds are required to complete the fourth task.

{1, 2, 3}

Returns: {1, 4, 6 }

{3, 2, 2, 1}

Returns: {8, 6, 7, 4 }

{2, 4, 7, 7, 3, 2, 9, 10, 5, 8, 10, 1, 5, 7, 6, 8, 10, 4, 9, 7, 10, 4, 3, 9}

Returns: 
{25, 69, 118, 119, 51, 30, 140, 147, 92, 133, 148, 12, 95, 124, 111, 135, 149, 82, 144, 128, 150, 86, 67, 146 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9730

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13485&pm=9730

Writer:

bmerry

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Simulation