Problem Statement
More specifically, Fabian wants to divide the line of filing cabinets into N sections (where N is the number of workers) so that every cabinet that the ith worker looks through is earlier in the line than every cabinet that the jth worker has to look through, for i < j.
His initial thought was to make all the sections equal, giving each worker the same number of filing cabinets to look through, but then he realized that the filing cabinets differed in the number of folders they contained. He now has decided to partition the filing cabinets so as to minimize the maximum number of folders that a worker would have to look through. For example, suppose there were three workers and nine filing cabinets with the following number of folders:
- 10 20 30 40 50 60 70 80 90
He would divide up the filing cabinets into the following sections:
- 10 20 30 40 50 | 60 70 | 80 90
The worker assigned to the first section would have to look through 150 folders. The worker assigned to the second section would have to search through 130 folders, and the last worker would filter through 170 folders. In this partitioning, the maximum number of folders that a worker looks through is 170. No other partitioning has less than 170 folders in the largest partition.
Write a class FairWorkload with a method getMostWork which takes a
Definition
- Class:
- FairWorkload
- Method:
- getMostWork
- Parameters:
- int[], int
- Returns:
- int
- Method signature:
- int getMostWork(int[] folders, int workers)
- (be sure your method is public)
Constraints
- folders will contain between 2 and 15 elements, inclusive
- Each element of folders will be between 1 and 1000, inclusive
- workers will be between 1 and the number of elements in folders, inclusive
Examples
{ 10, 20, 30, 40, 50, 60, 70, 80, 90 }
3
Returns: 170
This is the example from above.
{ 10, 20, 30, 40, 50, 60, 70, 80, 90 }
5
Returns: 110
With the addition of two more workers, it makes more sense to partition the books as follows: 10 20 30 40 | 50 60 | 70 | 80 | 90 The most folders that any single worker must look through will be 110.
{ 568, 712, 412, 231, 241, 393, 865, 287, 128, 457, 238, 98, 980, 23, 782 }
4
Returns: 1785
The filing cabinets should be partitioned as follows: 568 712 412 | 231 241 393 865 | 287 128 457 238 98 | 980 23 782
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000 }
2
Returns: 1000
The only fair partitioning gives the 14 cabinets with 1 folder to one worker, and the last cabinet with 1000 folders to the other worker.
{ 50, 50, 50, 50, 50, 50, 50 }
2
Returns: 200
There are two valid partitions: 50 50 50 | 50 50 50 50 50 50 50 50 | 50 50 50 Both of these partitions result in a maximum of 200 folders for any worker.
{1,1,1,1,100}
5
Returns: 100
With 5 workers, each worker gets a filing cabinet, and the most folders that any worker has to look through will be 100.
{ 950, 650, 250, 250, 350, 100, 650, 150, 150, 700 }
6
Returns: 950
With 6 workers, the maximum amount of folders that any worker would have to look through is 950. There are 25 different ways of partitioning the filing cabinets to produce this maximum: 950 | 650 | 250 | 250 350 | 100 650 150 | 150 700 950 | 650 | 250 | 250 350 100 | 650 150 | 150 700 950 | 650 | 250 | 250 350 100 | 650 150 150 | 700 950 | 650 | 250 250 | 350 | 100 650 150 | 150 700 950 | 650 | 250 250 | 350 100 | 650 150 | 150 700 950 | 650 | 250 250 | 350 100 | 650 150 150 | 700 950 | 650 | 250 250 350 | 100 | 650 150 | 150 700 950 | 650 | 250 250 350 | 100 | 650 150 150 | 700 950 | 650 | 250 250 350 | 100 650 | 150 | 150 700 950 | 650 | 250 250 350 | 100 650 | 150 150 | 700 950 | 650 | 250 250 350 | 100 650 150 | 150 | 700 950 | 650 | 250 250 350 100 | 650 | 150 | 150 700 950 | 650 | 250 250 350 100 | 650 | 150 150 | 700 950 | 650 | 250 250 350 100 | 650 150 | 150 | 700 950 | 650 250 | 250 | 350 | 100 650 150 | 150 700 950 | 650 250 | 250 | 350 100 | 650 150 | 150 700 950 | 650 250 | 250 | 350 100 | 650 150 150 | 700 950 | 650 250 | 250 350 | 100 | 650 150 | 150 700 950 | 650 250 | 250 350 | 100 | 650 150 150 | 700 950 | 650 250 | 250 350 | 100 650 | 150 | 150 700 950 | 650 250 | 250 350 | 100 650 | 150 150 | 700 950 | 650 250 | 250 350 | 100 650 150 | 150 | 700 950 | 650 250 | 250 350 100 | 650 | 150 | 150 700 950 | 650 250 | 250 350 100 | 650 | 150 150 | 700 950 | 650 250 | 250 350 100 | 650 150 | 150 | 700
{ 689, 516, 776, 244, 991, 797 }
5
Returns: 1020
{ 444, 976, 369 }
1
Returns: 1789
{ 845, 335, 950, 324, 345, 558 }
2
Returns: 2130
{ 208, 916, 724, 185, 33, 292, 792, 23, 720 }
1
Returns: 3893
{ 961, 37, 126, 508, 247, 572, 286 }
3
Returns: 961
{ 496, 477, 832, 670, 367, 231, 36, 741, 648, 259, 773, 557, 784 }
5
Returns: 1680
{ 962, 400, 598, 497, 873, 671, 465, 372, 922, 965, 645 }
5
Returns: 1759
{ 646, 321, 347, 684, 273, 718, 429, 842, 559, 893, 717, 971 }
2
Returns: 3982
{ 101, 653, 661, 310, 977 }
5
Returns: 977
{ 669, 331 }
1
Returns: 1000
{ 64, 498, 364, 970, 901, 352, 289, 76, 67, 805, 471, 787, 983, 649 }
8
Returns: 1253
{ 613, 723, 680, 518, 727, 60, 495, 322, 707, 94, 582, 755, 410, 340 }
7
Returns: 1336
{ 759, 746, 460, 92, 283, 739, 502, 501, 980, 86, 212, 276, 306, 571, 940 }
8
Returns: 1206
{ 30, 142, 706, 67, 303, 474, 930, 959, 325, 14, 995, 103, 113, 433, 564 }
8
Returns: 995
{ 320, 543, 187, 87, 710, 653, 333, 135, 674, 54, 739, 528, 930, 807, 503 }
8
Returns: 1267
{ 261, 575, 597, 217, 623, 620, 11, 946, 912, 575, 8, 728, 244, 248, 802 }
7
Returns: 1311
{ 722, 235, 642, 251, 105, 860, 532, 980, 483, 256, 226, 256, 799, 761, 200 }
9
Returns: 980
{ 10, 20, 30, 40, 50, 60, 70, 80, 90 }
3
Returns: 170
{ 1000, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
4
Returns: 1000
{ 100, 1, 1, 1, 1 }
5
Returns: 100
{ 1, 1, 1, 1, 1, 1, 1, 1000 }
3
Returns: 1000
{ 950, 650, 250, 250, 350, 100, 650, 150, 150, 700, 200, 170, 320, 100 }
7
Returns: 950