208. Truck Loading
A warehouse has several kinds of boxes. In boxTypes[i] = [count, units], count is how many identical boxes of kind i are available and units is how many items fit inside each one of them.
A truck can carry at most truckSize boxes in total, of any kinds. You may take any number of boxes from each kind, up to what is available. Return the largest total number of items you can put on the truck.
For instance, with the kinds [1, 9] and [4, 2] and room for 3 boxes, the best load is the 9-item box plus two 2-item boxes, which is 13 items.
Example 1
- Input:
- boxTypes = [[2,5],[3,2],[1,9]], truckSize = 4
- Output:
- 21
- Explanation:
Take the single 9-item box, both 5-item boxes and one 2-item box: 9 + 10 + 2 = 21.
Example 2
- Input:
- boxTypes = [[5,3]], truckSize = 2
- Output:
- 6
- Explanation:
Only 2 boxes fit and each holds 3 items, so 6.
Example 3
- Input:
- boxTypes = [[1,1],[1,2]], truckSize = 10
- Output:
- 3
- Explanation:
The truck has room for everything: 1 + 2 = 3 items.
Constraints
1 ≤ boxTypes.length ≤ 1000
1 ≤ count, units ≤ 1000
1 ≤ truckSize ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(1)