algoadvance

You are assigned to put some amount of boxes onto one 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 should 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: 
- There are 1 box of type [1,3] (3 units), 2 boxes of type [2,2] (4 units total), 3 boxes of type [3,1] (3 units total).
- You can take all the boxes of type [1,3], the two boxes of type [2,2], and one box of type [3,1].
- The total number of units = 3 + 4 + 1 = 8.

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

### Constraints
- 1 <= boxTypes.length <= 1000
- 1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
- 1 <= truckSize <= 10^6

## Clarifying Questions
1. Should we consider an upper limit for the number of boxes we can load beyond truck size?
    - No, the total number of boxes cannot exceed `truckSize`.
2. Can the number of units per box type vary significantly?
    - Yes, they can vary as each box type has its own units per box value.

## Strategy
1. **Sort Boxes by Units**: Sort the list of `boxTypes` by the `numberOfUnitsPerBox` in descending order because this maximizes the units loaded per box.
2. **Load Truck Greedily**:
    - Initialize `total_units` to 0.
    - Iterate through the sorted `boxTypes`.
    - For each box type, if the remaining truck size can include all boxes of this type, add all units to `total_units` and decrease `truckSize` accordingly.
    - If not, add as many boxes as possible until the truck is full and break.
3. **Return** the total units loaded.

## Code
```python
def maximumUnits(boxTypes, truckSize):
    # Sort the boxTypes by numberOfUnitsPerBox in descending order
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    
    total_units = 0
    
    for numberOfBoxes, numberOfUnitsPerBox in boxTypes:
        if truckSize >= numberOfBoxes:
            total_units += numberOfBoxes * numberOfUnitsPerBox
            truckSize -= numberOfBoxes
        else:
            total_units += truckSize * numberOfUnitsPerBox
            break
    
    return total_units

# Example usage:
# print(maximumUnits([[1,3],[2,2],[3,1]], 4))  # Output: 8
# print(maximumUnits([[5,10],[2,5],[4,7],[3,9]], 10))  # Output: 91

Time Complexity

  1. Sorting: This will take O(n log n) time where n is the number of box types.
  2. Iteration: This will take O(n) time since we iterate through the sorted list once.

Thus, the overall time complexity is O(n log n). The space complexity is O(1) auxiliary space, assuming that the input list boxTypes is modified in place by the sort operation.

Try our interview co-pilot at AlgoAdvance.com