Description Link to heading

1710.maximum-units-on-a-truck

Solution Link to heading

Sort boxTypes by the units that the box can load, then put the box of which the units are maximum on the truck one by one.

The time complexity can be decreased to $O(n)$ by using quick select.

Code Link to heading 

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;
    }
};