问题描述
解题思路
根据每个箱子可以装载的单元数量从大到小对boxTypes排序，然后每次将单元数量最大的箱子填入卡车。
使用快速选择算法可以将时间复杂度降低到$O(n)$。
代码
class Solution {
public:
int maximumUnits(vector<vector<int>> &boxTypes, int truckSize) {
std::sort(boxTypes.begin(), boxTypes.end(), [&](vector<int> vec1, vector<int> vec2) { return vec1[1] >= vec2[1]; });
int cnt = 0, sum = 0;
for (int i = 0; i < boxTypes.size(); i++) {
if (cnt + boxTypes[i][0] <= truckSize) {
sum += boxTypes[i][0] * boxTypes[i][1];
cnt += boxTypes[i][0];
} else {
sum += (truckSize - cnt) * boxTypes[i][1];
break;
}
}
return sum;
}
};