Maximum Units on a Truck

easyOA Simulation: 2 problems in 90 min each round17 stepsJava · Python · C++

Load at most truckSize boxes to maximise total units. Every box takes one slot, so take boxes with the most units per box first: sort types by units descending and fill greedily.

▶ Watch the animated trace

Traced input: boxTypes = [[1, 3], [2, 2], [3, 1]], truckSize = 4 → 8. Original problem: leetcode.com/problems/maximum-units-on-a-truck/

Complexity

BestO(n log n)

AverageO(n log n)

WorstO(n log n)

SpaceO(1)

Sorting dominates; counting sort works since units ≤ 1000.

Key idea

All boxes cost the same space, so value per box is all that matters.
Take as many of the best type as fit, then move to the next.
Stop when the truck is full.

Common mistakes

Sorting by the number of boxes instead of units per box.
Forgetting to cap the last type at the remaining space.

Solution

Java

int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes, (a, b) -> Integer.compare(b[1], a[1]));
    int total = 0;
    for (int i = 0; i < boxTypes.length && truckSize > 0; i++) {
        int take = Math.min(truckSize, boxTypes[i][0]);
        total += take * boxTypes[i][1];
        truckSize -= take;
    }
    return total;
}

Python

def maximumUnits(boxTypes: List[List[int]], truckSize: int) -> int:
    boxTypes.sort(key=lambda b: -b[1])
    total = 0
    for count, units in boxTypes:
        if truckSize == 0: break
        take = min(truckSize, count)
        total += take * units
        truckSize -= take
    return total

C++

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(), [](auto& a, auto& b) { return a[1] > b[1]; });
    int total = 0;
    for (size_t i = 0; i < boxTypes.size() && truckSize > 0; i++) {
        int take = min(truckSize, boxTypes[i][0]);
        total += take * boxTypes[i][1];
        truckSize -= take;
    }
    return total;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Truck bigger than supply Take everything.	`boxTypes = [[1, 5]], truckSize = 10`	`5`
Partial last type 5×10 + 3×9 + 2×7 = 91.	`boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]], truckSize = 10`	`91`
Truck size 1 One box with 9 units.	`boxTypes = [[3, 1], [1, 9]], truckSize = 1`	`9`