Start learning free

LESSON 325 OF 338 · GREEDY

Maximum Units on a Truck in Go: Greedy with sort.Slice

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

    GO · GREEDY

    Maximum Units On A Truck in Go, explained

    Problem overview

    The function maximumUnits receives boxTypes, a slice of pairs where boxTypes[i] = [numberOfBoxes, numberOfUnitsPerBox], and an integer truckSize, the maximum number of boxes the truck holds. It returns the most units you can load.

    In the first example, boxTypes = [[1,3],[2,2],[3,1]] and truckSize = 4. Take the one box with 3 units, the two boxes with 2 units each, and one of the boxes with 1 unit: 3 + 4 + 1 = 8. In the second example, [[5,10],[2,5],[4,7],[3,9]] with truckSize = 10, the best load is 5 boxes of 10 units, 3 of 9 and 2 of 7, which makes 50 + 27 + 14 = 91.

    Approach: densest boxes first

    Every box takes exactly one slot, whatever it holds, so the slots are the scarce resource and each slot should carry as many units as possible. That points to a greedy rule: sort the box types by units per box, largest first, and fill the truck from the front. When a type has more boxes than the truck has room for, take only what fits and stop.

    Why is this safe? Suppose a load used a box with fewer units while a denser box was left behind. Swapping them keeps the box count and never lowers the total. So some best load always consists of the densest boxes available.

    Tracing the second example: sorted by units per box, the types are 10, 9, 7 and 5. The truck has 10 slots. The first type has 5 boxes, so take all 5 for 50 units, leaving 5 slots. The second has 3 boxes, so take all 3 for 27 units, leaving 2. The third has 4 boxes but only 2 slots remain, so take 2 for 14 units. The truck is full, and the total is 91. The type with 5 units per box is never touched.

    Step by step

    1. Sort boxTypes in place with sort.Slice, by units per box in decreasing order. The less function gets two indices and reports that box i comes first when its units per box (index 1 of the pair) is larger.
    2. Declare units as the running total, starting at 0.
    3. Range over the sorted types, ignoring the index and binding each pair to box. Here box[0] is the number of boxes and box[1] the units in each.
    4. Compute take as min(box[0], truckSize). You can't load more boxes than the type has, nor more than the room left.
    5. Add take * box[1] to units.
    6. Subtract take from truckSize, and break when it reaches 0. The break is a shortcut: later iterations would take 0 anyway.
    7. Return units.

    The solution in Go

    func maximumUnits(boxTypes [][]int, truckSize int) int {
    sort.Slice(boxTypes, func(i, j int) bool {
        return boxTypes[i][1] > boxTypes[j][1]
    })
    units := 0
    for _, box := range boxTypes {
        take := min(box[0], truckSize)
        units += take * box[1]
        truckSize -= take
        if truckSize == 0 {
            break
        }
    }
    return units
}

    The Go details worth knowing:

    • sort.Slice sorts a slice in place using a function you supply. The function receives indices, not values, so it must look the elements up in the slice itself. It returns true when element i must come before element j, so > gives a decreasing order. The solution needs import "sort".
    • The input is changed. Sorting in place reorders the caller's boxTypes. For the second example it becomes [[5 10] [3 9] [4 7] [2 5]]. Copy the slice first if the caller needs the original order.
    • [][]int is a slice of slices. Each box is itself a slice, so box[0] and box[1] are indexed like any slice. Nothing in the type enforces that there are exactly two elements.
    • min is a built-in since Go 1.21, so no helper function and no import are needed.
    • truckSize is a copy. Integers are passed by value, so decrementing the parameter does not affect the caller's variable.

    Complexity

    Sorting costs O(n log n) for n box types, and the loop is O(n), so the total is O(n log n). Extra space is O(1) beyond what the sort uses internally. The numbers stay small with the stated limits: at most one million boxes of at most 1000 units each is under a billion units, which fits easily in a 64-bit int.

    Edge cases and common mistakes

    • Sorting by the wrong element. The key is box[1], the units per box. Sorting by the number of boxes, box[0], gives wrong answers.
    • Sorting in the wrong direction. With < the least dense boxes load first.
    • A truck bigger than the cargo. If the loop ends without the truck filling, every box is loaded and the total is returned. For [[1,1],[1,2]] and truckSize = 100 the answer is 3.
    • A partly loaded type. For [[5,10]] and truckSize = 3, take is 3 and the answer is 30.
    • Multiplying the wrong amounts. Add take * box[1], not box[0] * box[1], or a type that doesn't fully fit is overcounted.
    • A truck of size 0. The first take is 0, the total stays 0, and the loop breaks at once.

    Testing

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