We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Units on a Truck

Number: 1829

Difficulty: Easy

Paid? No

Companies: IBM, Amazon, Salesforce, Arista Networks, J.P. Morgan, Apple, Adobe

Problem Description

You are given an array of boxTypes, where each boxType is represented as [numberOfBoxes, numberOfUnitsPerBox]. You also have a truck that can carry at most truckSize boxes. The goal is to maximize the total number of units loaded onto the truck by selecting boxes in an optimal way.

Key Insights

  • Sort the boxTypes based on numberOfUnitsPerBox in descending order.
  • Greedily choose boxes with the highest units first.
  • Stop once the truck is full (i.e., truckSize boxes are loaded).

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of box types.
Space Complexity: O(1) if sorting is done in-place (excluding output storage).

Solution

The solution involves using a greedy algorithm. First, sort the boxTypes by the number of units per box in descending order. Then, iterate through the sorted list and at each step, decide how many boxes to take from the current box type. If the truck can accommodate all boxes of that type, take them; otherwise, take only as many boxes as can fit. Continue until the truck is full. The main data structure used is the list/array for storing box types, and the primary operation is sorting.

Code Solutions

# Python solution with line-by-line comments

def maximumUnits(boxTypes, truckSize):
    # Sort the boxTypes based on the number of units per box in descending order.
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    
    total_units = 0  # Variable to store the total units loaded.
    
    # Iterate through each box type.
    for boxes, units in boxTypes:
        # Determine how many boxes to take: minimum of available boxes and remaining truck capacity.
        boxes_to_take = min(boxes, truckSize)
        
        # Increase total units based on the boxes taken.
        total_units += boxes_to_take * units
        
        # Decrease the remaining truck size.
        truckSize -= boxes_to_take
        
        # If the truck is full, break out of the loop.
        if truckSize == 0:
            break
    
    return total_units

# Example usage:
print(maximumUnits([[1,3],[2,2],[3,1]], 4))  # Output should be 8
← Back to All Questions