LeetCode 1710 Maximum Units on a Truck

LeetCode

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub>]:

numberOfBoxes<sub>i</sub> is the number of boxes of type i. numberOfUnitsPerBox<sub>i</sub>is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1  3) + (2  2) + (1  1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints: 1 <= boxTypes.length <= 1000
1 <= numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub> <= 1000 1 <= truckSize <= 10<sup>6</sup>

题目大意：

货车能装的最大unit数，每种类型的盒都能装一定数量的units，而每种盒子占地方一样。

解题思路：

由于每种盒子占地一样，所以当然是先放unit大的。贪婪法。

解题步骤：

N/A

注意事项：

1. 按unit数倒序排序
2. pair是一个数组，要加pair[i][0]

Python代码：

def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
	pairs = [(li[1], li[0]) for li in boxTypes]
	pairs.sort(reverse=True)
	res, i = 0, 0
	for pair in pairs:
		res += pair[0] * min(pair[1], truckSize)
		truckSize -= pair[1]
		if truckSize <= 0:
			break
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)