Maximum Units on a Truck
Problem
Given boxTypes[i] = [numBoxes, unitsPerBox] and truckSize, return the maximum total units that fit.
boxTypes = [[1,3],[2,2],[3,1]], truckSize = 48def maximum_units(boxTypes, truckSize):
boxTypes.sort(key=lambda b: -b[1])
ans = 0
for cnt, u in boxTypes:
take = min(cnt, truckSize)
ans += take * u
truckSize -= take
if truckSize == 0: break
return ansfunction maximumUnits(boxTypes, truckSize) {
boxTypes.sort((a, b) => b[1] - a[1]);
let ans = 0;
for (const [cnt, u] of boxTypes) {
const take = Math.min(cnt, truckSize);
ans += take * u; truckSize -= take;
if (truckSize === 0) break;
}
return ans;
}class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
int ans = 0;
for (int[] b : boxTypes) {
int take = Math.min(b[0], truckSize);
ans += take * b[1];
truckSize -= take;
if (truckSize == 0) break;
}
return ans;
}
}int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), [](auto& a, auto& b){ return a[1] > b[1]; });
int ans = 0;
for (auto& b : boxTypes) {
int take = min(b[0], truckSize);
ans += take * b[1]; truckSize -= take;
if (truckSize == 0) break;
}
return ans;
}Explanation
The truck only holds so many boxes, so every slot should carry as many units as possible. The greedy rule is obvious once you see it: always load the boxes with the most units each first.
So we sort the box types by unitsPerBox in descending order. Then we go down the list, taking as many boxes of the current type as will fit: take = min(cnt, truckSize).
Each time we add take * u units to the answer and shrink the remaining truckSize. The moment the truck is full (truckSize == 0) we stop.
Example: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4. Sorted by units: [1,3], [2,2], [3,1]. Take the one 3-unit box, both 2-unit boxes, then one 1-unit box.
That fills all 4 slots: 1*3 + 2*2 + 1*1 = 8 units. Grabbing the richest boxes first guarantees the maximum.