Code Logo

Maximum Units on a Truck

Published at24 Jul 2026
Created by
Easy 0 views
Like0

You are given boxTypes where each element [numberOfBoxes, unitsPerBox] represents the number of boxes of a given type and how many units each box contains. truckSize is the maximum number of boxes the truck can carry. Return the maximum total units that can be loaded.

Sort boxTypes by unitsPerBox in descending order. Greedily take boxes from the highest value first. For each box type, take as many as possible up to truckSize, adding units times taken to the total. Decrement truckSize by the number of boxes taken.

Time is O(n log n) for sorting, O(n) for the greedy pass. Space is O(1) beyond the input. Edge cases include empty boxTypes (return 0), truckSize of zero (return 0), and having more capacity than total boxes (all boxes fit).

The greedy strategy of taking the highest-value boxes first is optimal because each box occupies exactly one unit of truck capacity regardless of its value. Sorting by units per box in descending order maximizes total value for the given capacity constraint.

This is a classic fractional knapSack problem variant where items are grouped by type and each box is indivisible but boxes of the same type are identical.

The greedy approach is optimal because the problem exhibits the matroid property where taking the highest-value remaining box always leads to the global optimum for the capacity constraint.

Example Input & Output

Example 1
Input
[[1,5]], 5
Output
5
Explanation

Take all boxes.

Example 2
Input
[[5,10],[2,5],[4,7],[3,9]], 10
Output
91
Explanation

Take 5 of 10=50, 3 of 9=27, 2 of 7=14. Total=91.

Example 3
Input
[[1,5]], 0
Output
0
Explanation

Truck size 0.

Example 4
Input
[[2,1],[2,2]], 3
Output
5
Explanation

Take 2 of 2=4, 1 of 1=1. Total=5.

Example 5
Input
[[1,3],[2,2],[3,1]], 4
Output
8
Explanation

Take 1 box of 3 (3), 2 of 2 (4), 1 of 1 (1). Total=8.

Algorithm Flow

Recommendation Algorithm Flow for Maximum Units on a Truck
Recommendation Algorithm Flow for Maximum Units on a Truck

Solution Approach

Sort by units per box descending. Greedily take boxes until truck is full.

function solution(boxTypes, truckSize) {
  boxTypes.sort(function(a,b){return b[1]-a[1];});
  var total = 0;
  for (var i = 0; i < boxTypes.length && truckSize > 0; i++) {
    var take = Math.min(boxTypes[i][0], truckSize);
    total += take * boxTypes[i][1];
    truckSize -= take;
  }
  return total;
}

Time O(n log n), Space O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes,(a,b)->b[1]-a[1]);
        int t=0;
        for (int[] b:boxTypes) {
            if (truckSize<=0) break;
            int take=Math.min(b[0],truckSize);
            t+=take*b[1];
            truckSize-=take;
        }
        return t;
    }
}