TopCoder problem "BatchSystem" used in SRM 481 (Division II Level Three)

Problem Statement

    In the past, whole organizations depended on a single, big computer to do all the computational work. In a particular case, a computer has a list of pending jobs which is described by int[] duration and String[] user. There are n pending jobs and each job is described by these two arrays. For the i-th job, duration[i] is the total time in minutes required to complete the job and user[i] is a string that identifies the user that requested that job. A user may request multiple jobs. The computer may only process one job at a time. The waiting time for a user is defined as the time that this user has to wait before all of the jobs (s)he requested are finished. Your program must schedule the jobs in such a way that the average waiting time over all users is minimized.

Return a int[] containing the 0-based indices of the n jobs in the order in which they should be processed. If there are multiple possible results, return the one that comes first lexicographically.


Parameters:int[], String[]
Method signature:int[] schedule(int[] duration, String[] user)
(be sure your method is public)


-The lexicographically earlier of two int[]s of the same length is the one that has the smaller element in the first position at which they differ.
-User names are case sensitive. A user named "Bob" is different from a user named "bob". See example 3 for clarification.


-duration will contain between 1 and 50 elements, inclusive.
-user will contain the same number of elements as duration.
-Each element of duration will be between 1 and 1000000000, inclusive.
-Each element of user will contain between 1 and 50 characters, inclusive.
-Each element of user will contain only letters ('a'-'z','A'-'Z') and at most one space character that will not be a leading or trailing space.


{400, 100, 100, 100}
{"Danny Messer", "Stella Bonasera", "Stella Bonasera", "Mac Taylor"}
Returns: {3, 1, 2, 0 }
In total, Mac Taylor will have to wait 100 minutes, Stella Bonasera 300 minutes and Danny Messer 700 minutes. The best average time is approximately 366.66 minutes.
{200, 200, 200}
{"Gil", "Sarah", "Warrick"}
Returns: {0, 1, 2 }
{100, 200, 50}
{"Horatio Caine", "horatio caine", "YEAAAAAAH"}
Returns: {2, 0, 1 }

Problem url:

Problem stats url:




PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories: