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 |
| 0) | |
| | {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. |
|
|
| 1) | |
| | {200, 200, 200} | {"Gil", "Sarah", "Warrick"} |
| Returns: {0, 1, 2 } | |
|
| 2) | |
| | {100, 200, 50} | {"Horatio Caine", "horatio caine", "YEAAAAAAH"} |
| Returns: {2, 0, 1 } | |
|