You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesi is the number of boxes of type i.numberOfUnitsPerBoxi 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
Constraints:
1 <= boxTypes.length <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 10^6
The description was taken from https://leetcode.com/problems/maximum-units-on-a-truck.
#O(N(Log N)) Time, O(N) Space
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
heap = []
total, boxes = 0, 0
for num_boxes, units_per in boxTypes:
heapq.heappush(heap, (-units_per, -num_boxes))
while heap: units_per, num_boxes = heapq.heappop(heap)
vacant = truckSize - boxes
total += -units_per * min(vacant, -num_boxes)
boxes += min(vacant, -num_boxes)
if boxes >= truckSize:
break
return totalThis problem is a very good introduction to greedy algorithms.
Greedy algorithms are implemented by sorting the input and taking care of the cheapest or most expensive tasks first to conserve the most resources.
In this case, the resource we would like to conserve is the space for each box. We are wanting to be greedy with the units because we are trying to find the maximum amount of units we can store in the given truck size.
If we have a restricted count of boxes we can store, and we are wanting to store the most units, we need to prioritize the boxes with the highest units-per-box to fulfill this task and be greedy with these boxes, choosing these boxes first because they are the least expensive.
What we will do is utilize a max-heap to sort the units. We will continuously pop the top of the max heap, add the units for each box, and once we run out of capacity, we will return the total amount of units we were able to store.
Let's initialize our heap, as well as the units and total counters.
heap = []
total, boxes = 0, 0
Next, let's push each unit count and number of boxes from the input into our max heap.
In Python, we can create a make-shift max-heap from the built-in min-heap, by negating each value so that the largest negative value is the smallest value in the heap so it will be at the top.
It is also important that we order the unit count first into the heap since it is what the heap will sort on.
for num_boxes, units_per in boxTypes:
heapq.heappush(heap, (-units_per, -num_boxes))
Once we have everything in the heap, we will start adding the boxes to the truck.
while heap:
During each iteration, we will pop the maximum units per box and its box count off of the heap.
units_per, num_boxes = heapq.heappop(heap)
We will multiply the number of boxes by the units per box and add it to the total, then add the number of boxes to our count.
But, it is crucial we don't exceed the box capacity on the truck, so what we will do is at the beginning of each iteration we will calculate how many vacant spots we have on the truck. This way, we don't exceed that value when we're adding units or boxes.
vacant = truckSize - boxes
Then, we will add to the total, the units per box multiplied by the minimum between the vacant slots and the number of boxes we have so that we don't exceed the vacant value.
Also, remember that for each value we pop from the stack we are going to have to negate again so that they are positive.
total += -units_per * min(vacant, -num_boxes)
Similarly, we will add the minimum between the vacant slots and the number of boxes we have so that we don't exceed the vacant value.
boxes += min(vacant, -num_boxes)
If we have met the truck size from the number of boxes we have just placed, we will break.
if boxes >= truckSize:
break
Once we have the most boxes we can, prioritizing the number of units per box, we will return the total number of units we were able to fit.
return total