TopCoder problem "ShipLoading" used in SRM 415 (Division I Level One)



Problem Statement

    You have to load a ship with some cargo. All the cargo is put in boxes. There are some cranes and each of them can put one box in the ship per minute. All cranes can work simultaneously. Each crane has a weight limit - it cannot move a box whose weight is greater than that limit. Return the minimal time (measured in minutes) needed to load the ship with all cargo or -1 if it is impossible.

You are given a int[] cranes, the i-th element of which is the weight limit of the i-th crane. You are also given a String[] boxes. Concatenate the elements of boxes to get a space-separated list of the boxes' weights.
 

Definition

    
Class:ShipLoading
Method:minimumTime
Parameters:int[], String[]
Returns:int
Method signature:int minimumTime(int[] cranes, String[] boxes)
(be sure your method is public)
    
 

Constraints

-cranes will contain between 1 and 50 elements, inclusive.

-boxes will contain between 1 and 50 elements, inclusive.

-Each element of boxes will contain between 0 and 50 characters, inclusive.
-The concatenation of all elements of boxes will be a non-empty space-separated list of integers with no leading zeroes. It will contain no leading, trailing, or consecutive spaces.

-Each element of cranes will be between 1 and 1,000,000, inclusive.

-Each box weight will be between 1 and 1,000,000, inclusive.

 

Examples

0)
    
{6,8,9}
{"2 5 2 4 7"}
Returns: 2
Everything can be done in 2 minutes.
1)
    
{19,20}
{"14 12 16 19 16 1 5"}
Returns: 4
Only two cranes, but each of them can move any of the boxes.
2)
    
{23,32,25,28}
{"5 27 10 16 24 20 2 32 18 7"}
Returns: 3
3)
    
{11,17,5,2,20,7,5,5,20,7}
{"18 18 15 15 17"}
Returns: 2
4)
    
{56,114,979,120,120,87,480}
{"221 882 504 358 642 674 212 679 203 279 632 799 79","6 502 275 823 372 594 482 343"}
Returns: 12
Note that you should not add spaces between elements of boxes during their concatenation.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9933

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13506&pm=9933

Writer:

Gluk

Testers:

PabloGilberto , bmerry , Olexiy , ivan_metelsky

Problem categories:

Greedy, Sorting