Maximum Units on a Truck
Easy · Greedy · Array · Greedy · Sorting
Problem
You are loading one truck. boxTypes[i] = [count_i, units_i] means there are count_i boxes of type i, and each of them holds units_i units.
The truck holds at most truckSize boxes, in any mix of types. Return the largest total number of units the truck can carry.
Examples
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 Output: 8
Take the 3-unit box, both 2-unit boxes and one 1-unit box: 3 + 4 + 1 = 8.
Input: boxTypes = [[3,2]], truckSize = 10 Output: 6
Only 3 boxes exist, so all of them go on: 3 · 2 = 6.
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 Output: 91
Take 5 boxes of 10, 3 of 9 and 2 of 7: 50 + 27 + 14 = 91.
Constraints
- 1 <= len(boxTypes) <= 1000
- 1 <= count_i, units_i <= 1000
- 1 <= truckSize <= 10^6
Approaches
- Repeatedly pick the richest type left — time O(n²), space O(n)
Follow-up
What if boxes also had different weights and the truck had a weight limit instead of a box limit? Then a slot is no longer worth the same for every box: if boxes may be split it is the fractional knapsack (sort by units per weight), and if they may not it is the 0/1 knapsack, which needs dynamic programming.
Related problems
Start free on Cariara · Coding problems · System design studio
