BatchSystem
SRM 481 · 2010-03-12 · by vexorian
SRM 481 · 2010-03-12 · by vexorian · Greedy
Problem Statement
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.
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.
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 }
3)
{1000000000,1000000000,1000000000,1000000000,1,2,3}
{"X","X","X","X","Y","Y","Y"}
Returns: {4, 5, 6, 0, 1, 2, 3 }
[overflow]
4)
{4,4,4,4,5,5,5,5,3,3,3,3,3}
{"X","x","X","x","X","x","X","x","X","x","X","x","X"}
Returns: {1, 3, 5, 7, 9, 11, 0, 2, 4, 6, 8, 10, 12 }
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BatchSystem with a public method vector<int> schedule(vector<int> duration, vector<string> user) · 119 test cases · 2 s / 256 MB per case