algoadvance

Leetcode 1710. Maximum Units on a Truck

Problem Statement

You are assigned to put some amount of boxes onto a truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You need to maximize the total number of units that can be put on the truck.

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: 
- Load 1 box of type [1,3] => 3 units.
- Load 2 boxes of type [2,2] => 4 units.
- Load 1 box of type [3,1] => 1 unit.
Total units = 3 + 4 + 1 = 8.

Example 2

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Clarifying Questions

  1. What are the constraints on the input sizes? ``` Constraints:
    • 1 <= boxTypes.length <= 1000
    • 1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
    • 1 <= truckSize <= 10^6 ```
  2. Do we need to consider the order of boxes while loading them onto the truck?
    • No, the order does not matter. You should prioritize loading boxes that have the highest number of units per box to maximize the total units.

Strategy

Since we want to maximize the number of units, we can use a greedy algorithm:

  1. Sort the array boxTypes based on the number of units per box in descending order.
  2. Iterate through the sorted list and start loading boxes onto the truck:
    • If the truck can take all boxes of the current type, load them and decrement the truck capacity accordingly.
    • If the truck can’t take all boxes of the current type, fill the remaining truck space with as many boxes as possible from the current type and stop.

Time Complexity

The overall time complexity would be (O(n \log n)).

Code

import java.util.Arrays;

public class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        // Step 1: Sort the boxTypes based on units per box in descending order
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        
        int maxUnits = 0;
        
        // Step 2: Load the truck with boxes
        for (int[] box : boxTypes) {
            int numberOfBoxes = box[0];
            int unitsPerBox = box[1];
            
            if (truckSize >= numberOfBoxes) {
                // If the truck can take all boxes of this type
                maxUnits += numberOfBoxes * unitsPerBox;
                truckSize -= numberOfBoxes;
            } else {
                // If the truck can only take part of the boxes of this type
                maxUnits += truckSize * unitsPerBox;
                break;
            }
        }
        
        return maxUnits;
    }
}

In this approach:

  1. We sort the boxTypes based on the units per box in descending order.
  2. We iterate through the sorted boxTypes to fill the truck as much as possible, focusing on the boxes with the most units first.

This ensures that we maximize the number of units loaded onto the truck.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI