1710. Maximum Units on a Truck - Detailed Explanation

Problem Statement

You’re given a list of box types boxTypes, where each element is a pair [numberOfBoxes, unitsPerBox]. You also have a truck that can carry at most truckSize boxes in total. Your goal is to load the truck so that the total number of units is maximized. Return that maximum total.

Examples

Example 1

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4  
Output: 8  
Explanation:  
 Take 1 box of type [1,3] → 1×3 = 3 units  
 Take 2 boxes of type [2,2] → 2×2 = 4 units  
 Remaining capacity = 4−(1+2)=1 box  
 Take 1 box of type [3,1] → 1×1 = 1 unit  
 Total = 3+4+1 = 8

Example 2

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10  
Output: 91  
Explanation:  
 Sort by unitsPerBox descending: [5,10],[3,9],[4,7],[2,5]  
 Fill in that order until truck holds 10 boxes  

Example 3

Input: boxTypes = [[1,5]], truckSize = 1  
Output: 5  

Constraints

• 1 ≤ boxTypes.length ≤ 10⁵
• boxTypes[i].length == 2
• 1 ≤ numberOfBoxes, unitsPerBox, truckSize ≤ 10⁵

Hints

1. If you want the most units per box, which box types should you load first?
2. Once you pick as many as possible of the highest‑unit box, move on to the next.
3. Sorting by unitsPerBox makes a greedy strategy optimal.

Greedy Sorting Approach

1. Sort boxTypes in descending order of unitsPerBox.
2. Initialize remaining = truckSize and totalUnits = 0.
3. Iterate through each [count, units] in the sorted list:
   • Let take = min(count, remaining).
   • Add take * units to totalUnits.
   • Decrease remaining by take.
   • If remaining == 0, break.
4. Return totalUnits.

Why This Is Correct

• At every step, you choose the box that gives the highest units per box.
• If you ever picked a lower‑unit box when a higher‑unit one was available, you’d lose out on potential units.
• Because there’s no penalty for mixing types, a simple sort + fill is globally optimal.

Step‑by‑Step Walkthrough (Example 1)

boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4

1. Sort by unitsPerBox → [[1,3],[2,2],[3,1]]
2. remaining=4, total=0

   - First type [1,3]: take = min(1,4)=1 → total+=1*3=3, remaining=3
   - Next    [2,2]: take = min(2,3)=2 → total+=2*2=4 (total=7), remaining=1
   - Next    [3,1]: take = min(3,1)=1 → total+=1*1=1 (total=8), remaining=0

3. remaining is 0 → stop  
Result = 8

Complexity Analysis

• Time:
  • Sorting takes O(m log m), where m = boxTypes.length.
  • One pass to accumulate takes O(m).
  • Overall: O(m log m).
• Space:
  • O(1) extra beyond the input (or O(m) if your language’s sort isn’t in‑place).

Python Code