1710. Maximum Units on a Truck
Problem Description
The given problem is a variation of the classical knapsack problem, where we're tasked with loading a truck with boxes. Each box contains a certain number of units, and each type of box has a corresponding number of units. We're provided with an array boxTypes
where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]
.
numberOfBoxes_i
tells us the number of available boxes of type i
and numberOfUnitsPerBox_i
indicates the number of units in each box of type i
.
We are also given truckSize
which represents the maximum number of boxes that fit onto the truck. Our goal is to maximize the total number of units loaded onto the truck without exceeding the truck size limit.
Intuition
The intuition behind the solution is based on a greedy algorithm. In order to maximize the number of units, we prioritize loading boxes with the highest number of units per box. This is because filling the truck with boxes that contain the most units will generally lead to a higher total number of units on the truck.
We start by sorting the boxTypes
array in descending order based on numberOfUnitsPerBox
, so the box types with the most units per box come first. This allows us to go through the boxTypes
array and add boxes to the truck in the order that maximizes the number of units.
For each type of box, we take as many boxes as we can until we either run out of that type of box or reach the truck's capacity. The number of units from each box type is added to our cumulative answer until the truck is full (when truckSize
becomes zero or negative).
If at any point the remaining truck size becomes less than the number of boxes available, we only take as many boxes as will fit in the truck, using the min
function. This ensures we do not exceed the truckSize
constraint.
By repeatedly choosing the boxes with the maximum units per box and keeping track of the remaining capacity on the truck, we can ensure that the final number of units is maximized.
Solution Approach
The provided solution uses a greedy algorithm to solve the problem of maximizing the number of units on the truck. Here is a step-by-step explanation of the implementation strategy:
-
Sorting the
boxTypes
array: The solution starts by sorting theboxTypes
array in descending order of the number of units per box. This is achieved by passing a custom lambda function to thesorted
method, which sorts based on the second element of each sub-array (-x[1]
). The negative sign indicates that we want a descending order.sorted(boxTypes, key=lambda x: -x[1])
-
Initializing the answer variable: A variable
ans
is initialized to store the total number of units that can be loaded onto the truck. -
Iterating through sorted
boxTypes
: The algorithm iterates over each box type in the sortedboxTypes
array. -
Calculating units to add: For each box type, the solution calculates how many units can be added. This is done by taking the minimum of the remaining
truckSize
and thenumberOfBoxes
of the current type, then multiplying it bynumberOfUnitsPerBox
to get the total units for that transaction.ans += b * min(truckSize, a)
-
Updating the remaining
truckSize
: After adding the units from the current box type to the answer, thetruckSize
is reduced by the number of boxes used, which isa
(representingnumberOfBoxes
).truckSize -= a
-
Checking if the truck is full: The loop will exit early using a
break
statement if there is no more capacity in the truck (truckSize <= 0
). This prevents unnecessary iterations once the truck is filled. -
Returning the result: Once the loop completes, whether by filling the truck or exhausting all box types, the total number of units
ans
is returned as the solution.
The use of sorting and a greedy approach is the key aspect of the algorithm, making sure that every step taken is optimal in terms of the number of units added per box. The for
loop along with the min
function and a simple accumulator variable (ans
) are the major elements in this simple and efficient implementation that guarantees the maximum number of units that can be loaded onto the truck within the given constraints.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Imagine we are given the following boxTypes
array and truckSize
:
boxTypes = [[1, 3], [2, 2], [3, 1]] truckSize = 4
The boxTypes
array consists of subarrays where the first element is the number of boxes and the second element is the number of units per box. Here:
- There is 1 box with 3 units per box.
- There are 2 boxes with 2 units per box.
- There are 3 boxes with 1 unit per box.
The truck can carry at most 4 boxes.
Step-by-Step Solution
-
First, we sort
boxTypes
based on the number of units per box in descending order:sorted(boxTypes, key=lambda x: -x[1])
After sorting, our
boxTypes
array looks like this:boxTypes = [[1, 3], [2, 2], [3, 1]]
Note that in this example, the array was already sorted, so it remains the same.
-
We initialize our answer variable,
ans
, to 0. It will accumulate the total units placed into the truck. -
We iterate through the sorted
boxTypes
array. Our goal is to consider box types with the most units first. -
For the first box type
[1, 3]
, we take the minimum oftruckSize
(which is 4) andnumberOfBoxes
(which is 1) multiplied bynumberOfUnitsPerBox
(which is 3).ans += 1 * min(4, 1) # Results in ans = 3 truckSize -= min(4, 1) # Decreases truckSize to 3
-
Next, for the second box type
[2, 2]
, we take the minimum of remainingtruckSize
(which is now 3) andnumberOfBoxes
(which is 2) multiplied bynumberOfUnitsPerBox
(which is 2).ans += 2 * min(3, 2) # Adds 4 to ans, resulting in ans = 7 truckSize -= min(3, 2) # Decreases truckSize to 1
-
Continuing, for the third box type
[3, 1]
, we again find the minimum of remainingtruckSize
(now 1) andnumberOfBoxes
(which is 3) multiplied bynumberOfUnitsPerBox
(which is 1).ans += 1 * min(1, 3) # Adds 1 to ans, resulting in ans = 8 truckSize -= min(1, 3) # Decreases truckSize to 0
-
Now, the truck is full (
truckSize
is now 0), so even though there are still boxes left, we cannot add more. -
Return the result: We've finished the process, and the
ans
variable now holds the value8
, which is the maximum number of units we can load into the truck given the constraints.
By following these steps using a greedy approach, we have maximized the number of units in our truck. The key was to prioritize the box types with the most units, aiming to fill the truck with the most valuable (unit-wise) boxes first, and then fill the remaining space with lower value boxes until the truck reaches capacity.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
5 # Initialize the maximum number of units the truck can carry.
6 max_units = 0
7
8 # Sort the box types by the number of units per box in a non-increasing order.
9 boxTypes.sort(key=lambda x: -x[1])
10
11 # Iterate through the box types.
12 for number_of_boxes, units_per_box in boxTypes:
13 # Calculate the number of boxes the truck can load
14 # by comparing what's left of the truck's capacity with the available boxes.
15 boxes_to_load = min(truckSize, number_of_boxes)
16
17 # Increment the maximum units by the units from the loaded boxes.
18 max_units += units_per_box * boxes_to_load
19
20 # Decrease the truckSize by the number of boxes loaded.
21 truckSize -= boxes_to_load
22
23 # If the truck is full, break out of the loop.
24 if truckSize <= 0:
25 break
26
27 # Return the total maximum units the truck can carry.
28 return max_units
29
1class Solution {
2 public int maximumUnits(int[][] boxTypes, int truckSize) {
3 // Sort the array of box types in descending order based on the number of units per box.
4 // This will help to maximize the number of units we can load onto the truck.
5 Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
6
7 // Initialize the result variable that will hold the maximum units.
8 int maxUnits = 0;
9
10 // Loop through the sorted boxTypes array.
11 for (int[] boxType : boxTypes) {
12 // Number of boxes of this type.
13 int numberOfBoxes = boxType[0];
14
15 // Number of units per box of this type.
16 int unitsPerBox = boxType[1];
17
18 // Calculate the number of boxes we can take of this type without exceeding truckSize,
19 // and add the number of units those boxes contribute to the total maxUnits.
20 maxUnits += unitsPerBox * Math.min(truckSize, numberOfBoxes);
21
22 // Subtract the number of boxes we've taken from the truckSize.
23 truckSize -= numberOfBoxes;
24
25 // If the truck is full, no need to continue checking other box types.
26 if (truckSize <= 0) {
27 break;
28 }
29 }
30
31 // Return the total maximum units we can carry in the truck.
32 return maxUnits;
33 }
34}
35
1class Solution {
2public:
3 int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
4 // Sort the box types based on the number of units per box in descending order
5 sort(boxTypes.begin(), boxTypes.end(), [](const auto& a, const auto& b) {
6 return a[1] > b[1];
7 });
8
9 int totalUnits = 0; // This will store the total number of units we can load on the truck
10
11 // Iterate through each type of box, since they are sorted we will pick the ones with
12 // the most units first, maximizing our total units carried
13 for (const auto& boxType : boxTypes) {
14 int numberOfBoxes = boxType[0]; // Number of boxes of this type
15 int unitsPerBox = boxType[1]; // Number of units per box for this type
16
17 // Calculate the number of boxes we can actually take of this type, which is the
18 // smaller between the number of boxes available, and the truck size remaining
19 int boxesToTake = min(truckSize, numberOfBoxes);
20
21 // Add the corresponding number of units to the total units
22 totalUnits += unitsPerBox * boxesToTake;
23
24 // Deduct the number of boxes taken from the truck's remaining capacity
25 truckSize -= boxesToTake;
26
27 // If the truck is full, we break out of the loop as we cannot load more boxes
28 if (truckSize <= 0) break;
29 }
30
31 // Return the total number of units that fit in the truck
32 return totalUnits;
33 }
34};
35
1function maximumUnits(boxTypes: number[][], truckSize: number): number {
2 // Sort the array of box types in descending order based on the number of units per box
3 boxTypes.sort((a, b) => b[1] - a[1]);
4
5 // Initialize the total number of units to add to the truck
6 let totalUnits = 0;
7
8 // Initialize the number of boxes accumulated on the truck
9 let boxesAccumulated = 0;
10
11 // Iterate through the sorted array of box types
12 for (const [numBoxes, unitsPerBox] of boxTypes) {
13 // If adding the current number of boxes doesn't exceed the truck size
14 if (boxesAccumulated + numBoxes < truckSize) {
15 // Add the units from all current boxes to the total
16 totalUnits += unitsPerBox * numBoxes;
17
18 // Add the current number of boxes to the accumulated count
19 boxesAccumulated += numBoxes;
20 } else {
21 // Calculate the remaining space on the truck
22 const remainingSpace = truckSize - boxesAccumulated;
23
24 // Add as many units as can fit in the remaining space and break
25 totalUnits += remainingSpace * unitsPerBox;
26 break;
27 }
28 }
29
30 // Return the total number of units that can be carried by the truck
31 return totalUnits;
32}
33
Time and Space Complexity
The time complexity of the provided code is O(n log n)
where n
is the length of the boxTypes
list. This is because the code sorts boxTypes
by the number of units in each box in descending order, which takes O(n log n)
time. After sorting, the code iterates through the boxTypes
list, which in the worst case takes O(n)
time if the truck can carry all boxes. However, sorting dominates the complexity. Therefore, the overall time complexity remains O(n log n)
.
The space complexity of the code is O(1)
as no additional space is used that scales with the input size. The sorting is done in-place (assuming the sort algorithm used by Python, Timsort, which has a space complexity of O(1)
for this scenario), and only a fixed number of variables are used regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!