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, each with n elements. duration[i] is the total time in minutes required to complete the i-th 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. The computer will always pick a schedule to process the jobs in such a way that the average of waiting times over all users is minimized. If there are multiple schedules that can accomplish the minimum average waiting time, the computer will pick any of them with equal probability.
We need a way to estimate how long the computer will take to finish each of the jobs. Your method must return a double[] containing n elements. The i-th element of your return must be the expected time in minutes before the computer finishes processing the i-th job. |
| |
Definition |
| | | Class: | BatchSystemRoulette | | Method: | expectedFinishTimes | | Parameters: | int[], String[] | | Returns: | double[] | | Method signature: | double[] expectedFinishTimes(int[] duration, String[] user) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | User names are case sensitive. A user named "Bob" is different from a user named "bob". See example 1 for clarification. |
| - | Each element of the returned value must have an absolute or relative error less than 1e-9. |
| |
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) | |
| | {3, 2, 4, 1} | {"Gil Grissom", "Sarah Sidle", "Warrick Brown", "Catherine Willows"} |
| Returns: {6.0, 3.0, 10.0, 1.0 } | | There is only one optimal way to schedule the jobs: {3, 1, 0, 2}. |
|
|
| 1) | |
| | {3, 2, 4, 1} | {"mac taylor", "Mac Taylor", "Mac Taylor", "Peyton Driscoll"} |
| Returns: {4.0, 8.0, 9.0, 1.0 } | | This time, there are two different ways to schedule the jobs that are optimal: {3, 0, 1, 2} and {3, 0, 2, 1}. |
|
|
| 2) | |
| | {13, 14, 15, 56, 56} | {"Tim Speedle", "Tim Speedle", "Tim Speedle", "Horatio Caine", "YEEEAAAAAAAAAAH"} |
| Returns: {27.5, 28.0, 28.5, 126.0, 126.0 } | |
|