BatchSystem | Topcoder Archive

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.

Definition

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

Notes

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.

Constraints

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.

Examples

```
{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 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.