1710. Maximum Units on a Truck
Model: qwen2.5-coder:14b
Topics: Greedy,Sort
FAANG asked: 1
Acceptance rate: 69.9%
Problem Breakdown
The problem requires us to maximize the number of units that can be loaded onto a truck given a set of box types and their respective unit counts. The input consists of a 2D array boxTypes, where each element is an array containing two integers: the first integer represents the number of boxes of a certain type, and the second integer represents the number of units in each box of that type. Additionally, we are given an integer truckSize which indicates the maximum number of boxes that can be loaded onto the truck.
Inputs:
boxTypes: A 2D array where each element is[numberOfBoxesi, numberOfUnitsPerBoxi].truckSize: An integer representing the maximum number of boxes that can be loaded onto the truck.
Outputs:
- The maximum total number of units that can be loaded onto the truck.
Implicit Constraints or Edge Cases:
- If
boxTypesis empty, the output should be 0. - If
truckSizeis 0, the output should be 0 regardless of the contents ofboxTypes. - Each box type has a positive number of boxes and units.
Intuition
A brute-force approach would involve checking all possible combinations of box types to see which combination yields the maximum number of units. However, this approach is computationally expensive with a time complexity of O(2^n), where n is the number of different box types, making it infeasible for larger inputs.
The key insight here is to prioritize loading boxes that contain more units per box first. This greedy strategy ensures that we maximize the total number of units loaded onto the truck without exceeding the truckSize. By sorting the box types based on the number of units per box in descending order, we can iteratively load as many boxes as possible from each type until the truck is full.
Approach
- Sort the Box Types: Sort the
boxTypesarray in descending order based on the number of units per box. - Initialize Variables: Initialize a variable
total_unitsto keep track of the total number of units loaded onto the truck and a variableremaining_boxesto keep track of the remaining capacity of the truck (truckSize). - Iterate Through Box Types: For each box type in the sorted array:
- Determine the number of boxes that can be loaded from this type, which is the minimum of the remaining capacity of the truck and the number of boxes available for this type.
- Add the units from these boxes to
total_units. - Decrease the
remaining_boxesby the number of boxes loaded. - If
remaining_boxesbecomes 0, break out of the loop as the truck is full.
- Return Result: Return the
total_units.
Complexity Analysis
- Time Complexity: O(n log n) due to the sorting step, where n is the number of different box types. The subsequent iteration through the sorted array takes linear time, O(n).
- Space Complexity: O(1) as we are using a constant amount of extra space.
Solution
def maximumUnits(boxTypes, truckSize):
# Sort box types by units per box in descending order
boxTypes.sort(key=lambda x: x[1], reverse=True)
total_units = 0
remaining_boxes = truckSize
for numberOfBoxes, unitsPerBox in boxTypes:
if remaining_boxes == 0:
break
# Load as many boxes as possible from this type
boxes_to_load = min(remaining_boxes, numberOfBoxes)
total_units += boxes_to_load * unitsPerBox
remaining_boxes -= boxes_to_load
return total_units
Edge Cases Handled
- Empty
boxTypes: The function returns 0 as there are no boxes to load. truckSizeis 0: The function immediately returns 0 without processing any box types.- All box types have the same number of units per box: The function correctly loads as many boxes as possible based on
truckSize. - Mixed box types with varying units per box: The function prioritizes loading boxes with higher units first, ensuring the maximum total units are loaded.