Start learning free

LESSON 358 OF 414 · GREEDY

Maximum Units on a Truck in Rust: 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 <= (number of box types) <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    RUST · GREEDY

    Maximum Units On A Truck in Rust, explained

    Problem overview

    The function maximum_units receives box_types, a vector of pairs where box_types[i][0] is how many boxes of type i exist and box_types[i][1] is how many units each of those boxes holds. It also receives truck_size, the maximum number of boxes the truck can carry. It returns the largest total number of units that fit on the truck.

    For box_types = [[1, 3], [2, 2], [3, 1]] and truck_size = 4, take the one box with 3 units, both boxes with 2 units, and one of the boxes with 1 unit: 1·3 + 2·2 + 1·1 = 8. For [[5, 10], [2, 5], [4, 7], [3, 9]] and a truck of 10 the answer is 91: five boxes of 10 units, three of 9 and two of 7.

    Approach: densest boxes first

    The truck is limited by the number of boxes, not by their weight, so every box costs one slot. A slot is best spent on a box that holds as many units as possible. That is the greedy rule: sort the box types by units per box, from largest to smallest, and load them in that order, taking as many of each type as still fit.

    Why is it safe? If an optimal load used a box with fewer units while a box with more units stayed behind, swapping them would not reduce the total. So some optimal load always takes the densest boxes first.

    Trace the second example. Sorted by units per box, the types are [5, 10], [3, 9], [4, 7] and [2, 5], and the truck has 10 free slots:

    • Take 5 boxes of 10 units: 50 units, 5 slots left.
    • Take 3 boxes of 9 units: 27 units, total 77, 2 slots left.
    • Take min(4, 2) = 2 boxes of 7 units: 14 units, total 91, 0 slots left. The truck is full.

    Step by step

    1. Sort box_types in place with sort_by, ordering by units per box in decreasing order. Comparing b[1] with a[1], in that order, gives the descending order.
    2. Start a running total units at 0.
    3. Loop over &box_types, binding each pair to box_t. Borrowing the vector avoids moving it into the loop.
    4. Decide how many boxes to take: box_t[0].min(truck_size). You can't take more boxes than the type has, nor more than the truck has room for.
    5. Add the units of those boxes, take * box_t[1], to the total.
    6. Shrink the free space by take. When it reaches 0 the truck is full, so leave the loop. This only saves work, because later iterations would take 0 anyway.
    7. Return units as the final expression.

    The solution in Rust

    impl Solution {
    fn maximum_units(mut box_types: Vec<Vec<i32>>, mut truck_size: i32) -> i32 {
        box_types.sort_by(|a, b| b[1].cmp(&a[1]));
        let mut units = 0;
        for box_t in &box_types {
            let take = box_t[0].min(truck_size);
            units += take * box_t[1];
            truck_size -= take;
            if truck_size == 0 {
                break;
            }
        }
        units
    }
}

    The Rust details worth a closer look:

    • mut in the signature. mut box_types lets the function sort its own vector, and mut truck_size lets it count the free space down. Both are local to the function: the caller's values are moved or copied in.
    • The comparator. sort_by takes a closure that returns an Ordering. b[1].cmp(&a[1]) compares the second argument with the first, so larger values sort first. Writing a[1].cmp(&b[1]) would sort ascending and load the least dense boxes first.
    • Integer min. box_t[0].min(truck_size) is a method call on an i32 that returns the smaller of the two values.
    • Stable sort. sort_by is stable, so types with equal units per box keep their original order. Here that doesn't change the total, because equal-density boxes are interchangeable.
    • units infers its type. It starts as a bare 0, and adding an i32 to it makes it an i32, matching the return type. Leaving off the semicolon on the last line returns it.

    Complexity

    Time: O(n log n), where n is the number of box types. The sort dominates, and the loop is a single pass.

    Space: O(1) beyond the input, since the sort happens in place and the loop keeps a few integers.

    Edge cases and common mistakes

    • A truck bigger than the supply. With [[2, 5]] and a truck of 10, the loop takes both boxes, finds truck_size still at 8, and ends normally. The answer is 10.
    • Sorting by the wrong field. Sorting by box_t[0], the count, rewards types with many boxes instead of many units.
    • Sorting ascending. This loads the worst boxes first. For the first example it would give a smaller total than 8.
    • Taking the whole type without a cap. Using box_t[0] instead of min(truck_size) overloads the truck, and truck_size goes negative, so the == 0 check never fires.
    • Overflow. Each loaded box holds at most 1000 units and the truck holds at most 1,000,000 boxes, so the total can't pass 1,000,000,000, which fits in an i32 (the limit is about 2.1 billion). With 1000 types of [1000, 1000] and a truck of 1,000,000, the function returns 1000000000.

    Testing

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