642. Maximum Units on a Truck
You are loading one truck that can carry at most truckSize boxes. The warehouse inventory is described by boxTypes, where boxTypes[i] = [numBoxes_i, unitsPerBox_i]: there are numBoxes_i identical boxes of type i, each containing unitsPerBox_i units of product.
You may take any number of boxes of each type, up to what's in stock, as long as the total box count does not exceed truckSize.
Return the maximum total number of units the truck can carry.
Example 1:
Input: boxTypes = [[1, 3], [2, 2], [3, 1]], truckSize = 4
Output: 8
Explanation: Load the single 3-unit box, both 2-unit boxes, and one 1-unit box: 3 + 2 + 2 + 1 = 8 units in 4 boxes.
Example 2:
Input: boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]], truckSize = 10
Output: 91
Explanation: Densest first: five 10-unit boxes, three 9-unit boxes, then two 7-unit boxes fill the last slots — 50 + 27 + 14 = 91.
Constraints:
- 1 ≤ boxTypes.length ≤ 1000
- 1 ≤ numBoxes_i, unitsPerBox_i ≤ 1000
- 1 ≤ truckSize ≤ 10⁶
Hints:
Every box costs exactly one slot of truck capacity, no matter how many units it holds. So a box with more units is always at least as good as a box with fewer.
Sort the box types by units per box, descending, and load greedily until the truck is full — take min(stock, remaining capacity) from each type.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: boxTypes = [[1, 3], [2, 2], [3, 1]], truckSize = 4
Expected output: 8