Maximum Units on a Truck

Easy Subject: Greedy

Time Complexity

O(N log N)

Space Complexity

O(1)

Problem Description

Problem Statement

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes, numberOfUnitsPerBox]. You are also given an integer 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

Optimal Solution

Python

Approach: Greedy Sort by Units

Sort the boxTypes array in descending order of units per box. Iterate through the sorted list, taking as many boxes as possible (up to the remaining truckSize) from the highest-unit box types first.

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: -x[1])
        total_units = 0

        for boxes, units in boxTypes:
            take = min(boxes, truckSize)
            total_units += take * units
            truckSize -= take
            if truckSize == 0:
                break

        return total_units