Maximum Units on a Truck

Share

Load at most truckSize boxes, each box type has a unit count. Maximize total units.

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

Solution Approach

Sort by units per box descending. Greedily take as many of highest-unit boxes as possible.

  • Sort boxTypes by units descending
  • For each box type: take min(available, remaining capacity)
  • Add boxes*units to result
  • Decrease remaining capacity
  • Stop when truck full
Java
public int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
    int units = 0, remaining = truckSize;
    for (int[] box : boxTypes) {
        int take = Math.min(box[0], remaining);
        units += take * box[1];
        remaining -= take;
        if (remaining == 0) break;
    }
    return units;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)