1710. Maximum Units on a Truck

Greedy

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






*/