Maximum Units on a Truck

LeetCode Problem 1710

Maximum Units on a Truck

Problem Statement:

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 the 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

Problem Solving Approach

We see that we need to maximize the number of units we get to fill in the available space of the truck. To do this we need to have a sorted list of the number of units of a particular box. The plan is to start from the maximum units a box can give and start filling the struck in the reverse order till the truck space is filled or no boxes are left to fill and return the total units the truck holds.

The sorting approach can be done in one of two ways:

  1. Store the boxTypes arrays in a descending priority queue so that the values are sorted wrt the units a box can hold.
  2. Since the constraints say that the maximum number of units per box is 1000, we can maintain a list of size 1000 where the index is the number of units a box can have and we store the number of boxes that contain index number of units in that list. This way we are sacrificing a bit of space for a increased speed up of the code.

Once we have this sorted data, we can pick the box that has the largest number of units and place it in the truck till there is no space left in the truck. We then return the maximum number of units in that truck.

Implementation

The following is the implementation where we use a priority queue to store the array in descending order of units:

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> Integer.compare(y[1], x[1]));
        // Store boxTypes array in the priority queue in descending order.
        for(int[] boxType: boxTypes) {
          queue.add(boxType);
        }
        int maximumUnits = 0;
        // Continue operation till the queue is empty or till there is no space left in the truck
        while((!queue.isEmpty()) && (truckSize > 0)) {
          int[] item = queue.poll();
          int spaceToFill = Math.min(truckSize, item[0]);
          maximumUnits += spaceToFill * item[1];
          truckSize -= spaceToFill;
        }
        return maximumUnits;
    }
}

The following is the implementation where we use a fixed List of length 1000:

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int[] totalBoxesForUnits = new int[1000];
        // Store a list where list[index] holds the number of boxes that holds index number of units.
        for(int[] box: boxTypes) {
          totalBoxesForUnits[box[1] - 1] += box[0];
        }
        int maximumUnits = 0;
        for(int i = 1000; i > 0 && truckSize > 0; i--) {
          // Number of boxes that can be taken to fill the space left in truck
          int spaceToFill = Math.min(truckSize, totalBoxesForUnits[i - 1]);
          // Keep track of the maximum units 
          maximumUnits += spaceToFill * i;
          // Remove the space filled from the truckSize
          truckSize -= spaceToFill;
        }
        return maximumUnits;
    }
}