Start learning free

LESSON 330 OF 344 · GREEDY

Maximum Units on a Truck in Python: Greedy with Sorting

Practice Greedy, O(n log n) Read the full explanation

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 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 <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    PYTHON · GREEDY

    Maximum Units On A Truck in Python, explained

    Problem overview

    The method maximumUnits receives boxTypes, a list of pairs [numberOfBoxes, numberOfUnitsPerBox], and an integer truckSize, the most boxes the truck can carry. Each box takes one slot whatever it holds. The method returns the largest total number of units that fit on the truck.

    In the first example, boxTypes = [[1, 3], [2, 2], [3, 1]] and truckSize = 4. Take the one box with 3 units, then the two boxes with 2 units, which makes 3 boxes and 7 units. One slot is left, and one box of the third type adds 1 more unit. The total is 8.

    Approach: fill the truck with the densest boxes first

    Every box uses exactly one of the truckSize slots, so the problem is about value per slot. A box with 9 units is always a better use of a slot than a box with 5. This suggests a greedy strategy: load boxes in order of units per box, from highest to lowest, until the truck is full or the boxes run out.

    The strategy is correct because of an exchange argument. Suppose an answer uses a box with fewer units while a box with more units is left behind. Swapping the first box for the second keeps the box count the same and doesn't lower the total. So some best answer takes the densest boxes first, and the greedy loading finds it.

    A brute-force search over every way to choose boxes grows exponentially, and even a smarter search is not needed here. Sorting plus one pass is enough.

    In the second example, [[5, 10], [2, 5], [4, 7], [3, 9]] with truckSize = 10, sorting by units per box gives the order 10, 9, 7, 5. Take 5 boxes of 10 units (50), then 3 boxes of 9 units (27), which leaves 2 slots. Two boxes of 7 units add 14, and the total is 91.

    Step by step

    1. Sort boxTypes in place by units per box, largest first. list.sort takes a key function. Python sorts in ascending order of the key, so using the negated units per box, -x[1], puts the highest units first.
    2. Start a running total in units, set to 0.
    3. Loop over the box types, unpacking each pair into boxes and units_per_box.
    4. Decide how many boxes to take from this type: take = min(boxes, truckSize). You can't load more boxes than the type has, nor more than the remaining space.
    5. Add their units and use up the space. Add take * units_per_box to units, and subtract take from truckSize, which now means the free slots.
    6. Stop when the truck is full. If truckSize == 0, break. This is only a shortcut, because later iterations would take 0 boxes anyway.
    7. Return units after the loop.

    The solution in Python

    class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: -x[1])
        units = 0
        for boxes, units_per_box in boxTypes:
            take = min(boxes, truckSize)
            units += take * units_per_box
            truckSize -= take
            if truckSize == 0:
                break
        return units

    The Python details worth a closer look:

    • The sort key. lambda x: -x[1] is a small anonymous function. It receives one inner list, such as [2, 5], and returns the negated second item. An alternative that reads more directly is boxTypes.sort(key=lambda x: x[1], reverse=True).
    • sort() works in place. It changes the caller's list and returns None. Writing boxTypes = boxTypes.sort(...) would replace the list with None. To keep the original order, use sorted(boxTypes, key=...), which returns a new list.
    • Tuple unpacking in the loop header. for boxes, units_per_box in boxTypes unpacks each two-item list into two names. It would fail if some entry did not have exactly two items.
    • Reusing a parameter. truckSize is a local name inside the method, so reassigning it with -= doesn't affect the caller's variable. Integers are immutable, so truckSize -= take just rebinds the name.
    • Large numbers need no care. Python integers don't overflow. The largest answer here is at most 10**6 * 1000, which would fit in most fixed-size types anyway.

    Complexity

    Time: O(n log n), where n is the number of box types. Sorting dominates. The loop that follows is O(n).

    Space: O(n) in the worst case for the sort, because Python's sort may use a temporary buffer. The rest of the method uses a few variables.

    Edge cases and common mistakes

    • The truck is bigger than all the boxes. [[1, 3]] with truckSize = 10 returns 3. The loop ends without the truck becoming full, and the break never runs.
    • The truck fills in the middle of a type. min(boxes, truckSize) takes just part of that type, which the first example does with the third type.
    • Sorting the wrong way. Without the negation, the loop takes the sparsest boxes first and returns a lower total.
    • Sorting by number of boxes. The first item in each pair is the count, and the units per box is the second item, x[1]. Sorting by x[0] orders the types by quantity, which doesn't help.
    • Multiplying the wrong numbers. The units are the number taken times units per box, not times the type's full box count.
    • The input list changes. After the call, the caller's boxTypes is sorted. If you need the original order, sort a copy.

    Testing

    • boxTypes = [[1, 3], [2, 2], [3, 1]], truckSize = 4 gives 8.
    • boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]], truckSize = 10 gives 91.
    • boxTypes = [[1, 3]], truckSize = 10 gives 3.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free