Start learning free

LESSON 330 OF 344 · GREEDY

Maximum Units on a Truck in Java: 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 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    JAVA · GREEDY

    Maximum Units On A Truck in Java, explained

    Problem overview

    The method maximumUnits receives a 2D array boxTypes and an integer truckSize. Each row is a pair [numberOfBoxes, numberOfUnitsPerBox]: how many boxes of that type exist, and how many units each one holds. The truck carries at most truckSize boxes, of any mix of types. The method returns the largest total number of units the truck can carry.

    With boxTypes = [[1,3],[2,2],[3,1]] and truckSize = 4, the best load is the one 3-unit box, both 2-unit boxes and one 1-unit box: 3 + 2 + 2 + 1 = 8. With [[5,10],[2,5],[4,7],[3,9]] and a truck of 10, the answer is 91.

    Approach: greedy, densest boxes first

    The limit is a number of boxes, not a weight or a volume, so every box takes exactly one slot, whatever it holds. Each slot should therefore carry as many units as possible. That suggests a greedy rule: always load the box with the most units that is still available.

    The rule is safe because of an exchange argument. Suppose a load uses a box with fewer units while a box with more units, still on the ground, could take its slot. Swapping them keeps the box count and doesn't lower the total. So some best load always contains the highest-unit boxes first.

    The row [numberOfBoxes, unitsPerBox] groups identical boxes, so there is no need to handle them one at a time. Sort the rows by unitsPerBox from largest to smallest. Then, for each row, take as many boxes as both the row and the remaining space allow.

    On the second example the sorted order is [5,10], [3,9], [4,7], [2,5]. The truck has 10 slots. Take 5 boxes of 10 units: 50. Take 3 boxes of 9 units: 27, running total 77, with 2 slots left. Take 2 of the 7-unit boxes: 14, for 91. The truck is full, so the remaining rows are never needed.

    Step by step

    1. Sort boxTypes in place with Arrays.sort and a comparator that orders by the second column, largest first.
    2. Declare units as an int starting at 0, the running total.
    3. Loop over the rows with a for-each loop whose variable is an int[] named box. Here box[0] is the count of boxes and box[1] is the units per box.
    4. Decide how many to take: Math.min(box[0], truckSize). The truck can't take more than the row has, nor more than the space left.
    5. Add the units and use up the space: add take * box[1] to units, and subtract take from truckSize.
    6. Stop when the truck is full. Once truckSize reaches 0, break. The loop would also work without this, since every later take would be 0, but stopping early skips useless rows.
    7. Return units after the loop.

    The solution in Java

    class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        int units = 0;
        for (int[] box : boxTypes) {
            int take = Math.min(box[0], truckSize);
            units += take * box[1];
            truckSize -= take;
            if (truckSize == 0) {
                break;
            }
        }
        return units;
    }
}

    Java details worth a closer look:

    • Sorting an int[][]. A 2D array is an array of int[] objects, so Arrays.sort can take a comparator for those rows. The lambda (a, b) -> b[1] - a[1] receives two rows and returns a negative number when a should come first. Putting b first in the subtraction gives descending order. A comparator can't be passed for a plain int[], only for arrays of objects, which includes the rows of this 2D array.
    • Subtraction in a comparator can overflow. Here every units value is between 1 and 1000, so b[1] - a[1] is safe. For arbitrary int values, Integer.compare(b[1], a[1]) is the version that can't overflow.
    • The input is changed. Sorting happens in place, so the caller's boxTypes comes back reordered. Parameters like truckSize are copies, so reducing it doesn't affect the caller's variable.
    • No overflow in the total. Each product is at most 1000 * 1000, and with at most 1000 rows of up to 1000 boxes, the largest possible total is about a billion, which fits in an int (maximum about 2.1 billion).

    Complexity

    Let m be the number of rows, boxTypes.length.

    Time: O(m log m). Sorting dominates. The loop then does constant work for each row, so it is O(m).

    Space: O(m) in the worst case for the sort. Sorting objects in Java uses a merge-based algorithm that may allocate a temporary array of references. The loop itself uses a few integers.

    The loop doesn't depend on truckSize: it moves from row to row, never box by box, so a truck of a million slots costs nothing extra.

    Edge cases and common mistakes

    • A truck bigger than all the boxes. With [[2,3]] and truckSize = 10, take is 2, the loop ends, and the result is 6. The truck is never full, so the break never fires.
    • A truck that fills in the middle of a row. In the first example, only one of the three 1-unit boxes is loaded. Taking box[0] blindly would overload the truck.
    • Sorting by the wrong column. Sorting by box[0], the number of boxes, ignores how much each box holds. The greedy argument is only about units per box.
    • Ascending order. Sorting the other way around loads the least valuable boxes first and gives too small an answer.
    • Multiplying before limiting. The units come from take * box[1], with take already limited. Using box[0] * box[1] counts boxes that never fit.
    • Equal units per box. Rows that tie can come in any order, since swapping them can't change the total.

    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 = [[2,3]], truckSize = 10 gives 6.
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free