1710. Maximum Units on a Truck

Problem Description

You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesᵢ, numberOfUnitsPerBoxᵢ]. numberOfBoxesᵢ represents the number of boxes of type i, and numberOfUnitsPerBoxᵢ represents the number of units in each box of type i. You also have an integer truckSize, representing the maximum number of boxes you can put on the truck. The goal is to determine the maximum total number of units that can be put on the truck.

Solution Approach

The optimal solution involves a greedy approach. We prioritize loading boxes with the highest number of units per box first. This ensures we maximize the total units carried within the truck's capacity.

1. Sort: Sort the boxTypes array in descending order based on numberOfUnitsPerBoxᵢ. This ensures that we consider the most valuable boxes first. Various sorting algorithms can be used (e.g., merge sort, quicksort), with time complexity typically O(n log n), where n is the number of box types.

2. Iterate and Load: Iterate through the sorted boxTypes. For each box type, determine how many boxes of that type can be loaded without exceeding truckSize. Load the maximum possible number of boxes of that type and update truckSize accordingly.

3. Calculate Total Units: Accumulate the total number of units loaded.

Time and Space Complexity Analysis

• Time Complexity: O(n log n) dominated by the sorting step. The iteration through the sorted array takes O(n) time.
• Space Complexity: O(1) (In-place sorting is possible; extra space used is constant). If a sorting algorithm requiring additional space is used, the space complexity would be O(log n) or O(n) depending on the algorithm.

Code Implementation (Python)

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: x[1], reverse=True) # Sort by units per box in descending order
        totalUnits = 0
        remainingTruckSize = truckSize
        
        for numBoxes, unitsPerBox in boxTypes:
            loadableBoxes = min(numBoxes, remainingTruckSize) # Load as many boxes as possible
            totalUnits += loadableBoxes * unitsPerBox
            remainingTruckSize -= loadableBoxes
            if remainingTruckSize == 0: # Truck is full; no need to continue
                break
        return totalUnits
 

Code Implementation (Java)

import java.util.Arrays;
import java.util.Comparator;
 
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]); // Sort by units per box in descending order
        int totalUnits = 0;
        int remainingTruckSize = truckSize;
 
        for (int[] boxType : boxTypes) {
            int loadableBoxes = Math.min(boxType[0], remainingTruckSize);
            totalUnits += loadableBoxes * boxType[1];
            remainingTruckSize -= loadableBoxes;
            if (remainingTruckSize == 0) {
                break;
            }
        }
        return totalUnits;
    }
}

Similar implementations can be created in other languages (C++, Javascript, Go, etc.) following the same algorithm. The core logic remains consistent across languages: sort by units per box, iterate, load boxes greedily, and accumulate units.