pick larger unit first, so sort by numberOfUnitsPerBoxi desc
ticky part is use left box number to gen the result (not like 背包問題, 只有一個包, 這裡有多個紙箱可以用, 所以可以用 貪心）
time: O(nlogn)
space: O(1)
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]); // sort by unit desc, use unit bigger one
int res = 0;
for (int boxType[] : boxTypes) {
int boxNum = Math.min(truckSize, boxType[0]); // use < truckSize's box number
res += boxNum * boxType[1];
truckSize -= boxNum;
if (truckSize == 0) {
return res;
}
}
return res;
}
}
/*
[[5,10],[3,9], [4,7], [2,5]]
10 , 5 use 5
5*10 = 50. 10-5 = 5
5, 3 use 3
27 3*9, 5-3 = 2
2 4 use 2
14 2*7 2, 4 = 2
= 91
boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]
maximum number of boxes: truckSize
You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.
maximum total number of units
1 + 2 + 1 => weight
5*10 50
3*9 27
*/
