Problem Statement
It is the beginning of the day at a bank, and a crowd of clients is already waiting for the entrance door to open. Once the bank opens, no more clients arrive, and tellerCount tellers begin serving the clients. A teller takes serviceTime minutes to serve each client. clientArrivals specifies how long each client has already been waiting at the moment when the bank door opens. Your program should determine the best way to arrange the clients into tellerCount queues, so that the waiting time of the client who waits longest is minimized. The waiting time of a client is the sum of the time the client waited outside before the bank opened, the time the client waited in a queue once the bank opened until the service began, and the service time of the client.
Return the minimum waiting time for the client who waits the longest.
Definition
- Class:
- OptimalQueues
- Method:
- minWaitingTime
- Parameters:
- int[], int, int
- Returns:
- int
- Method signature:
- int minWaitingTime(int[] clientArrivals, int tellerCount, int serviceTime)
- (be sure your method is public)
Constraints
- clientArrivals will contain between 1 and 50 elements, inclusive.
- Each element in clientArrivals will be 0 and 100, inclusive.
- tellerCount will be between 1 and 50, inclusive.
- serviceTime will be between 1 and 100, inclusive.
Examples
{1,2}
1
10
Returns: 21
If the client who waited 1 minute goes first, the second client will have to wait 2 + 10 + 10 = 22 minutes in total. It is better for the client who waited 2 minutes to go first because then the waiting times are 12 and 21.
{10}
50
50
Returns: 60
There is only one client who has waited 10 minutes, and the service time is 50 minutes, so the answer is 10 + 50 = 60.
{10,10,10}
2
20
Returns: 50
{2,4,6,3,5}
3
10
Returns: 23
{74,65,82,31,10,64,28,24,65,56}
5
8
Returns: 90
{86}
50
14
Returns: 100
{37,54,59,68,99,34,78,99,53,59,66,76,96,97,79,95,88,50,72,84,9,6,44,37,18,32,54,54,86,35,30,93,47,97,15,82,17,20,15,40,75,34,75,31,73,40,52,35,60,44}
1
100
Returns: 5006
{18,42,28,18,15,19,99,70,37,69,47,41,38,15,48,62,86,47,35,28,62,73,83,92,79,49,18,45,25,64,28,66,86,40,99,62,52,22,70,53,87,69,53,76,94,5,20,97,50,25}
50
31
Returns: 130
{53,47,23,33,7,39,10,88,94,18,50,0,99,60,42,82,22,93,43,13}
3
89
Returns: 630
{20,64,82,70,7,87,19,25,32,43,68,29,68,64,8,86,71,10,55,76,66,15,91,32,79,21,31,16,12,93,77,11,96,37,40,33,62,50,89,77,69,66,97,19,41,59,40,75,20,47}
18
57
Returns: 200
{64,62,56,3,47,46,52,98,54,75,89,56,27,19}
4
22
Returns: 120
{8,84,72,15,59,62,14,30,65,44,3,100,25,23,12,76,8,53,5,39,31,42,93,47,7,52,35,69,71,73,16,32,29,38,93,42,45,21,25}
6
93
Returns: 658
{0,62,60,79,94,86,30,86,83,94,41,56,56,20,72,41,92,80,73,38,57,55,76,4,42,41,0,22}
9
15
Returns: 109
{19,90}
1
92
Returns: 203
{85,75,0,27,60,29}
3
74
Returns: 177
{95,74,31,18,53,6,79,54,25,54,9}
5
100
Returns: 306
{44,52,58,57,41,41,2,50,23,98,45,28,92,17,11,11,45,54,55,100,30,99,27,95,90,74,41,8,63,10,37,64,93,81,19}
15
77
Returns: 242
{59,77}
1
23
Returns: 105
{71,73}
2
9
Returns: 82
{67,85,12,1,32,99,55,56,51,97,85,24,85,81,99,29,47,18,68,95,36,22,88,43,20,30,41,38,20,25,16,66,13,54,41,96,77,18,67,74,14,44,33,98,31,20}
30
13
Returns: 112
{22,85,41,82,78,78,11,37,77,25,18,71,42,93,31,98,92,56,84,77,55,61,60,65,38,93,86,42,56,90,72,75,59}
48
17
Returns: 115
{30,11,38,79,98}
1
72
Returns: 371
{92,1,12,66,100,8,7,26,26,84,77,70,75,19,83,40,92,39,87,97,93,54,42,32,33,33,35,73,78,56,26,28,42,79,15,56,91,8,96,10,69,44,28,34,58}
1
42
Returns: 1891
{87,9,35,60,35,89,91,51,95,24,36,30,88,65,97,17,25,38,24,13,9,86,36,25,56,59,92,68,37,78,43,55,61,42,85,38,8,48,78,66,94,95,96,27,49,1,48}
12
32
Returns: 155
{66,50,41,37,47,70,83,24,67,43,66,82,11,5,89,37,3,53,50,21,99,42,51,83,33,76,98,14,40,24}
2
1
Returns: 100
{1,41,90,47,66,31,66,34,63,7,0,17,95,71,58,15,69,28,32,33,4,44,0,70,18,48,88,79,18,18,71,6}
11
1
Returns: 96
{42,78,3,11,64,52,78,87,27,62,82,8,83,2,73,76,39,78,37,34,60,7,39,4,77,62,14,86,41,84,24,97,95,48,98,23,47,8,99,43,9,43,27,46,83,30,19}
3
25
Returns: 403
{83,68,24,28,9}
5
9
Returns: 92
{3,47,50,70,83,83,31,13,49,84,21,52,86,15,2,97,88,22,75,13,65,72,38,81,28,34,32}
13
27
Returns: 124
{8,25,89,97,32,58,65,75,66,79,63,54,48,38,5,32,70}
6
4
Returns: 101
{92,72,53,74,94,64,47,80,30,15,33,25,92,92,93,58,62,97,72,55,93,61,72,87,13,58,75,61,5,59,93,71,19,99,78,85,100,35,96,54,61,61,6,1,47,69,9,34}
37
59
Returns: 159
{53,67,23,86,60,85,45,29,40,11,79,85,20,92,29,18,88,40,97,83,14,5,82,93,6,81,28,99,11,20,17,23,36,1,46,66,2,0,18,65}
17
89
Returns: 278
{66,38,75,25,66,32,38,76,27,65,66,81,54,10,73,93,78,25,72,58,23,43,66,64,78,49,7,83,93,37,66,63,62,69,51,51,81,52,43,78,93,10,37,56,30,59,70}
31
38
Returns: 131
{26,73,72,87,17,3,19,35,84,87,94,86,49,76,73}
9
73
Returns: 195
{55,55,47,83,17,8,94,50,71,0,80,4,19,31,40,16,37,95,37,36,85,95,49,94,19,9,37,73}
21
36
Returns: 131
{51,83,9,1,61,61,93,74,36,49,84,92,56,11,15,59,60,10,47,14,13,10,74,21,33,18,86,5,30,98,8,85,13,18,92,19,17,56,34,18,76,47,33}
15
36
Returns: 134
{8,41,27,73,57,52,80,2,33,94,79,12,79,63,42,25,10,1,74,88,59,24,7,71,65,99,48,61,93,34,91,27}
7
29
Returns: 153
{73,85,90,29}
3
7
Returns: 97
{18,38,8,49,96,27,53,53,11,83,35,78,24,20,75,15,3,34,10,35,88,24,24,70,73,16,27,84,36,45,55,66,34,26,62,82,92}
9
28
Returns: 143
{30,7,46,10,81,1,92,18,21}
10
69
Returns: 161
{64,11,16,58}
10
95
Returns: 159
{35,92,14,25,14,55,77,75,49,14,83,22,57,3,92}
1
99
Returns: 1488
{93,5,61,89,94,1,64,96,51,98,36,18,97,89,63,38,100,96,71,66,10,28,9,68,67,37,72,5,82,92,63,51,23,65,83,7,57,52,59,51,41,39,100,32,46,99,48,90}
5
10
Returns: 121
{70,41,35,47,77,17,20}
7
81
Returns: 158
{35,0,49,8,75,72,95,9,60,95,61,48,88,49,17,53,26,43,83,7,45,53,14,41,63,76,64,10}
6
53
Returns: 274
{63,28,44,12,66,62,38,67,2,60,19,57,50,65,75,13,36,7,60,43,20,43,100,75,38,68,99,69,56,92,2,54,56,76,69,87,94,78,11,54,65,6,49,61,86,71,76,53}
2
67
Returns: 1610
{18,96,85,0,43}
6
42
Returns: 138
{91,92,2,85,23,89,75,58,88,47,44,56,33,35,74,99,39,100,76,65,83,34,72,52}
8
20
Returns: 120
{39,30,23,26,92,81,35,80,98,84,39,73,31,27,52,82}
10
91
Returns: 217
{36}
4
16
Returns: 52
{6,60,29,43,2,47,55,66,1,92,77,47,100,16,97,73,10,85,52,22,19,41,91,63,63,88,53,18,46,39,62,90,39,19,18,93,21,16,41,31,21,15,61}
7
21
Returns: 148
{69,48,77,93,33,69,75,38,42}
9
12
Returns: 105
{100,5,19,24,36,96,48,67,13,37,53,33,68,79,32,87,1,29,34,46,68,87,16,47,80,25,55,25,23,64,3,70,77,36,62,99,62,72,62,60,69,91,0,86,97}
3
21
Returns: 318
{46,82,30,25,58,73,56,1,96,28,62,42,83,5,36,97,57,43,14,30,24,94,65,9,15,23,100,74,74,81,85,73,27}
5
42
Returns: 303
{80,43,60,76,79,52,41,75,33,28,84,21,40,83,88,76,47,58,38,23,65,44,31,11,12,40,62,56,70,88,99,36,44,42,4,55,20}
4
46
Returns: 464
{28,29,88,1,56,71,39,55,42,34,26,15,36,58,34,70,20,21,88,60,50,7,34,72,0,22,13,39,44,48,33,63,77,39,92,82,38}
9
82
Returns: 410
{1,50,10,49,58,79,51}
6
58
Returns: 137
{11,74,85,79,9}
8
80
Returns: 165
{71,14,76,53,11,29,68,84,54,34,95,84,37,30,32,64,2,2,29,91,52,25,80,90,49,34,0,27,11,0,78,62,87,61,85,23,19,73,17,29,13,71,52,94,57}
6
27
Returns: 218
{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
1
100
Returns: 5100
{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
50
100
Returns: 200
{2, 4, 6, 3, 5 }
3
10
Returns: 23
{100, 1 }
1
1
Returns: 101
{0, 100, 27, 33, 45 }
3
13
Returns: 113
{10, 100, 5, 20 }
2
10
Returns: 110
{1, 2, 3, 4, 5 }
3
86
Returns: 174
{100, 1 }
1
10
Returns: 110
{0, 1, 2, 3, 4, 5 }
3
17
Returns: 36
{12, 14, 17, 19, 21, 24 }
4
10
Returns: 34
{1, 2, 4, 8 }
2
1
Returns: 9
{0, 0 }
1
1
Returns: 2
{2, 3, 4, 3 }
2
1
Returns: 5
{5, 2, 3, 4, 5 }
2
1
Returns: 6
{100, 99, 3, 1 }
2
1
Returns: 101
{2, 3 }
2
15
Returns: 18
{10, 20, 80, 90, 100 }
2
45
Returns: 170
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }
50
8
Returns: 58
{1, 2 }
2
10
Returns: 12
{1, 2, 6 }
2
1
Returns: 7
{0, 0, 0, 10, 100 }
1
1
Returns: 101
{1, 2, 3, 10, 11, 12, 22, 23, 24, 39, 40 }
3
1
Returns: 41
{100, 9, 8, 7, 6, 5, 4 }
5
10
Returns: 110
{100, 1, 1, 1, 1, 1, 1, 1, 1 }
1
5
Returns: 105
{22, 50, 2, 1, 12, 23, 51, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 7, 9, 7, 78, 6, 5, 8, 5, 6, 3, 4, 34, 11 }
4
7
Returns: 85
{0, 100 }
1
1
Returns: 101
{98, 99, 97, 89, 88, 74 }
3
1
Returns: 100
{100, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
3
1
Returns: 101
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 100 }
2
2
Returns: 102
{1, 17, 21 }
2
1
Returns: 22
{100, 99, 1 }
2
5
Returns: 105
{1, 2, 3, 4, 5, 6, 7, 8 }
2
20
Returns: 82
{1, 20, 21 }
1
10
Returns: 40
{10, 20, 10, 10 }
2
1
Returns: 21
{6, 6, 6, 6, 6, 1 }
5
1
Returns: 7
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
1
100
Returns: 5000
{1, 7, 15, 27 }
10
1
Returns: 28
{1, 10, 10 }
1
2
Returns: 14
{1, 2, 3, 50 }
2
1
Returns: 51
{1, 2, 3 }
1
10
Returns: 31
{1, 30 }
1
1
Returns: 31
{1, 1, 1, 1 }
4
1
Returns: 2
{20, 5, 10, 15, 25, 30 }
1
100
Returns: 605
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 100 }
10
2
Returns: 102
{2, 2, 2, 2, 10, 10, 10, 10 }
2
3
Returns: 16
{1, 2, 33 }
2
2
Returns: 35
{2, 4, 6, 3, 20 }
3
10
Returns: 30
{1, 4, 2, 3, 6, 8, 7, 9 }
4
10
Returns: 24
{100, 90, 60, 50, 30, 20, 10 }
3
10
Returns: 110
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
1
20
Returns: 221
{1, 100 }
1
10
Returns: 110