Problem Description
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]:
- numberOfBoxes_i is the number of boxes of type i.
- numberOfUnitsPerBox_i is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.
Return the maximum total number of units that can be put on the truck.
Key Insights
- Prioritize boxes that contain more units per box.
- Sort the boxTypes array based on the number of units per box in descending order.
- Greedily select boxes until the truck is full or there are no more boxes left.
Space and Time Complexity
Time Complexity: O(n log n) - due to the sorting step. Space Complexity: O(1) - no additional data structures used apart from input storage.
Solution
The approach to solve this problem involves sorting the boxTypes array based on the number of units per box in descending order. After sorting, we iterate through the sorted list and greedily add boxes to the truck until we reach the truck size limit. We keep track of the total units added to the truck.