Solution

Method 1 – Greedy Sorting by Units

Intuition

To maximize the total units on the truck, we should prioritize box types with the highest units per box. By sorting box types in descending order of units per box, we can greedily fill the truck with the most valuable boxes first.

Approach

Sort boxTypes by numberOfUnitsPerBox in descending order.
Initialize ans to 0 and iterate through sorted box types:
- For each type, take as many boxes as possible (up to truckSize).
- Add the units to ans and decrease truckSize accordingly.
- Stop if the truck is full.
Return the total units loaded.

Complexity

⏰ Time complexity: O(n log n) — Sorting box types.
🧺 Space complexity: O(1) — In-place sorting and constant extra space.

Code

Related Tags