Start learning free

LESSON 359 OF 415 · GREEDY

Maximum Units on a Truck in Swift: Greedy Sort by Units per Box

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

    SWIFT · GREEDY

    Maximum Units On A Truck in Swift, explained

    Problem overview

    The method maximumUnits receives boxTypes and truckSize. Each element of boxTypes is a pair [numberOfBoxes, unitsPerBox]: how many boxes of that type exist and how many units each one holds. The truck takes at most truckSize boxes in total, whatever their type. The method returns the largest total number of units that can be loaded.

    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 each, which makes 3 boxes and 7 units. One slot is left, and the best remaining box holds 1 unit, so the total is 8. In the second example, [[5,10],[2,5],[4,7],[3,9]] with a truck of 10 gives 91.

    Approach: load the densest boxes first

    Every box takes exactly one slot, no matter how many units it holds. A slot used for a 10-unit box is therefore worth more than a slot used for a 5-unit box. That makes the problem greedy: always fill the next free slot with the best box still available.

    Sort the box types by units per box, largest first. Then go through them in order. For each type, load as many boxes as you can: all of them, or as many as there are free slots, whichever is smaller. Stop when the truck is full.

    Trace example 2 after sorting: the order is [5,10], [3,9], [4,7], [2,5]. The truck has 10 slots. Five boxes of 10 units give 50 and leave 5 slots. Three boxes of 9 give 27 and leave 2. From the third type only 2 of the 4 boxes fit, giving 14. The total is 50 + 27 + 14 = 91, and the truck is full.

    Why is this correct? Suppose a load skipped a denser box while carrying a less dense one. Swapping the two boxes keeps the box count the same and doesn't lower the total. So some best load always uses the densest boxes first.

    Step by step

    1. Sort the box types by units per box in decreasing order into a new constant, sortedBoxes. The closure compares the second element of each pair and returns true when the first pair should come first.
    2. Make the capacity mutable. Swift parameters are constants, so declare a new var truckSize that starts with the parameter's value. Also declare the running total units as var, starting at 0.
    3. Loop over sortedBoxes with the variable box. Here box[0] is the number of boxes of this type and box[1] is the units per box.
    4. Decide how many to take. take is the smaller of the boxes available and the slots left.
    5. Add the units. That is take * box[1].
    6. Use up the slots. Subtract take from truckSize, and break when it reaches 0. The loop would finish correctly without the break, because take would be 0 from then on, but stopping early saves work.
    7. Return units after the loop.

    The solution in Swift

    class Solution {
    func maximumUnits(_ boxTypes: [[Int]], _ truckSize: Int) -> Int {
        let sortedBoxes = boxTypes.sorted { $0[1] > $1[1] }
        var truckSize = truckSize
        var units = 0
        for box in sortedBoxes {
            let take = min(box[0], truckSize)
            units += take * box[1]
            truckSize -= take
            if truckSize == 0 {
                break
            }
        }
        return units
    }
}

    The Swift details worth a closer look:

    • sorted returns a new array. The input boxTypes is left as it was, which is why sortedBoxes can be a let. The in-place version, sort, would need a var.
    • Shorthand arguments. In { $0[1] > $1[1] }, $0 and $1 are the two pairs being compared. A closure with a single expression returns that expression without writing return.
    • Shadowing. var truckSize = truckSize creates a new local variable with the same name. On the right-hand side the name still refers to the parameter. From then on, the name means the mutable copy.
    • Global min. Swift's free function min(_:_:) returns the smaller of two values.
    • Overflow. Swift's Int is 64 bits, and an overflowing multiplication would stop the program. Here the product is at most 1000 * 1000, so there is no risk.

    Complexity

    Let n be the number of box types.

    Time: O(n log n). The sort takes O(n log n) and the loop runs at most n times with constant work in each.

    Space: O(n). sorted builds a new array of the same size. The loop itself needs only two integers.

    Edge cases and common mistakes

    • The truck is bigger than the supply. With [[1,3]] and a truck of 10 the loop takes the only box and ends with slots to spare. The result is 3.
    • The truck fills part-way through a type. min(box[0], truckSize) takes only what fits, as in the example where 2 of the 4 boxes of the 7-unit type are used.
    • Sorting by the wrong element. Sorting by $0[0], the number of boxes, ignores what matters. Sorting ascending by units fills the truck with the worst boxes.
    • Taking whole types only. Boxes can be split across the truck's limit, so a type may be taken partially.
    • Modifying truckSize without a copy. Assigning to a parameter is a compile error in Swift.
    • Multiplying the wrong values. Units are take * box[1], not box[0] * box[1], unless every box of that type fits.

    Testing

    • [[1,3],[2,2],[3,1]], truck 4 gives 8.
    • [[5,10],[2,5],[4,7],[3,9]], truck 10 gives 91.
    • [[1,3]], truck 10 gives 3.
    • [[2,1],[3,5]], truck 4 gives 16: three boxes of 5 units and one of 1.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free