You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes
, where boxTypes[i] = [numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub>]
:
numberOfBoxes<sub>i</sub>
is the number of boxes of type i
.numberOfUnitsPerBox<sub>i</sub>
is the number of units in each box of the type i
.You are also given an integer truckSize
, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize
.
Return the maximum total number of units that can be put on the truck.
Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
How would you approach this problem? What is the optimal time and space complexity?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach for this problem involves exploring every single possible way to load boxes onto the truck. We try every combination of box types until we find the best one that fits within the truck's capacity.
Here's how the algorithm would work step-by-step:
def maximum_units_brute_force(box_types, truck_size):
maximum_units = 0
def solve(current_box_index, current_truck_size, current_units):
nonlocal maximum_units
# If the truck is full, update the max units and stop
if current_truck_size == 0:
maximum_units = max(maximum_units, current_units)
return
# If we have considered all box types, update and stop
if current_box_index == len(box_types):
maximum_units = max(maximum_units, current_units)
return
number_of_boxes, units_per_box = box_types[current_box_index]
# Iterate through all possible number of boxes of this type
for box_count in range(min(number_of_boxes, current_truck_size) + 1):
# Recursively call to include or exclude the box type
solve(
current_box_index + 1,
current_truck_size - box_count,
current_units + box_count * units_per_box
)
solve(0, truck_size, 0)
return maximum_units
To maximize the units on the truck, we should prioritize loading boxes with the highest number of units per box. This approach avoids inefficiently filling the truck with boxes that hold fewer units and ensures we grab the most valuable boxes first. The goal is to greedily pick from the most unit-dense boxes until the truck is full.
Here's how the algorithm would work step-by-step:
def maximum_units(box_types, truck_size):
# Sort box types by units per box in descending order
box_types.sort(key=lambda box: box[1], reverse=True)
total_units = 0
space_remaining = truck_size
for box_count, units_per_box in box_types:
# Load as many boxes of the current type as possible
if space_remaining >= box_count:
total_units += box_count * units_per_box
space_remaining -= box_count
# Truck is full, exit the loop
else:
total_units += space_remaining * units_per_box
space_remaining = 0
break
return total_units
Case | How to Handle |
---|---|
Empty boxTypes array | Return 0 since there are no boxes to load. |
truckSize is 0 | Return 0 as the truck cannot carry any boxes. |
All box types have 0 boxes available | Return 0 as there are no boxes to load, even if truckSize is non-zero. |
A box type has a negative number of boxes | Treat the number of boxes as 0 for that type, or throw an exception, depending on problem constraints. |
A box type has negative units per box | Treat the units per box as 0 for that type, or throw an exception, depending on problem constraints. |
truckSize is larger than the total number of boxes available | Load all available boxes and return the total units. |
Integer overflow when calculating total units | Use a data type with a larger range (e.g., long) to store the result. |
Large number of box types, each with a small number of boxes and small units per box | Sorting dominates the runtime, but given the problem constraints, this may be acceptable. Consider specialized sorting if needed. |