#1710
Maximum Units on a Truck
Easy Fractional-knapsack style
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Box types come as [count, unitsPerBox]. A truck holds at most truckSize boxes. Maximise the total units loaded.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: load boxes to maximise units, limited by the number of boxes.
Why this works: every box uses one slot, so take the boxes with the most units first.
Example: [[1,3],[2,2],[3,1]], truck 4
1 box × 3, 2 boxes × 2, 1 box × 13 + 4 + 1 = 8
✦Hints open one at a time
Every box takes one slot, so take the boxes with the most units first.
Sort by units per box, descending.
↗Approach
This is the "fractional knapsack" idea with equal weights: sort by value per box and fill greedily, taking min(count, remaining slots) of each type.
</>Solution (Java)
import java.util.*;
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]); // most units per box first
int units = 0;
for (int[] t : boxTypes) {
int take = Math.min(t[0], truckSize);
units += take * t[1];
truckSize -= take;
if (truckSize == 0) break;
}
return units;
}
}!Common mistake
Sorting by box count instead of units per box.
Complexity
- Time: O(n log n).
- Space: O(log n) for sorting.
Topic: Greedy
🎬 Episodes 69–73: video coming soon