Start learning free

LESSON 329 OF 343 · GREEDY

Maximum Units on a Truck in C++: Greedy with Sorting

Practice Greedy, O(n log n) Read the full explanation

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

  • numberOfBoxesi is the number of boxes of type i.
  • numberOfUnitsPerBoxi is the number of units in each box of 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 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    C++ · GREEDY

    Maximum Units On A Truck in C++, explained

    Problem overview

    The method maximumUnits receives boxTypes, a vector of pairs [numberOfBoxes, unitsPerBox], and an integer truckSize, the most boxes the truck can carry. You choose any boxes, at most truckSize of them, and the method returns the largest total number of units that can be loaded.

    In the first example, boxTypes = [[1,3],[2,2],[3,1]] and truckSize = 4. Take the one box of 3 units, both boxes of 2 units, and one of the three boxes of 1 unit. That is 4 boxes and 3 + 4 + 1 = 8 units. In the second example, [[5,10],[2,5],[4,7],[3,9]] with truckSize = 10, the answer is 91.

    Approach: fill the truck with the richest boxes first

    Every box takes exactly one slot, no matter how many units it holds. So each slot should hold the best box still available. That makes the problem a natural fit for a greedy strategy: sort the box types by units per box, largest first, and load boxes from the front until the truck is full or the types run out.

    Why is greedy correct here? Suppose some best loading skips a box with more units in favour of a box with fewer. Swapping the smaller box for the larger one keeps the box count the same and does not lower the total. So you can always push the solution towards "richest first" without losing anything.

    The number of boxes within a type matters only as a limit. For each type, you load as many as you can: all of them, or however many slots remain.

    On the second example, sorted by units per box: [5,10], [3,9], [4,7], [2,5]. Load 5 boxes of 10 units (50), then 3 of 9 (27, total 77) and the truck has 2 slots left. Of the 4 boxes with 7 units, take 2 (14), total 91, and the truck is full.

    Step by step

    1. Sort boxTypes in place by the second column, decreasing, using sort with a lambda comparator. The comparator returns true when its first argument should come before the second, so a[1] > b[1] orders by units per box, largest first.
    2. Declare units as an int set to 0 to hold the running total.
    3. Loop over the types with a range-based for and a loop variable box declared const auto&. Here box[0] is how many boxes of the type exist, and box[1] is the units in each.
    4. Decide how many to take: take = min(box[0], truckSize). You can't take more boxes than exist, and you can't take more than the truck has room for.
    5. Update the totals. Add take * box[1] to units and subtract take from truckSize. The parameter now means the remaining capacity.
    6. Stop when the truck is full. If truckSize == 0, break. The loop would also finish correctly without this, since take would be 0 from then on, but there is no reason to keep going.
    7. Return units after the loop.

    The solution in C++

    class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](const auto& a, const auto& b) {
            return a[1] > b[1];
        });
        int units = 0;
        for (const auto& box : boxTypes) {
            int take = min(box[0], truckSize);
            units += take * box[1];
            truckSize -= take;
            if (truckSize == 0) {
                break;
            }
        }
        return units;
    }
};

    The details specific to C++:

    • The comparator. std::sort accepts any callable as a third argument. The lambda [](const auto& a, const auto& b) { return a[1] > b[1]; } takes two rows by reference without copying them. Its parameters are declared with auto, which makes it a generic lambda, and that is valid C++14 and later. The comparison must be strict (>, not >=). A comparator that returns true for equal elements breaks the rules of the sort and can crash it.
    • Sorting changes the caller's data. boxTypes is passed as vector<vector<int>>&, so the sort reorders the vector the caller gave you. That is acceptable here. If it weren't, you would take the parameter by value or sort a copy.
    • Swapping rows is cheap. A vector is moved by exchanging its internal pointers, not by copying its elements, so sorting a vector of vectors does not copy the pairs.
    • const auto& in the loop reads each row in place. Plain auto would copy every inner vector.
    • min needs both arguments to have the same type. Both box[0] and truckSize are int, so it compiles. Mixing an int and a size_t would be an error.
    • Overflow. Each loaded box holds at most 1,000 units, and at most 1,000,000 boxes are loaded, so units never exceeds 1,000,000,000. That fits in a signed 32-bit int, whose maximum is about 2.1 billion. Signed overflow is undefined behaviour in C++, so it is worth checking such a bound.

    Complexity

    Time: O(m log m), where m is the number of box types. The sort dominates. The loop is one pass of constant work per type.

    Space: O(1) extra beyond the sort's own small bookkeeping. The sort works in place, and the method keeps just a few integers.

    Edge cases and common mistakes

    • Not enough boxes to fill the truck. With [[1,3]] and truckSize = 5 the answer is 3. The loop ends after the only type, and the truck stays partly empty.
    • Sorting by the wrong column. Sorting by box[0] orders by how many boxes there are, which has nothing to do with the value of one slot.
    • Sorting ascending. Using < in the comparator loads the poorest boxes first and gives a smaller total.
    • Taking the whole type. Adding box[0] * box[1] without the min would overfill the truck when only part of a type fits.
    • Forgetting to reduce the capacity. If truckSize never shrinks, every type is taken in full.
    • Equal units per box. Types with the same units can come in any order. The total is the same either way, so no tie-break is needed.

    Testing

    • [[1,3],[2,2],[3,1]] with truckSize = 4 gives 8.
    • [[5,10],[2,5],[4,7],[3,9]] with truckSize = 10 gives 91.
    • [[1,3]] with truckSize = 5 gives 3.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free