Solution: Maximum Units on a Truck
Tags: algorithms, javascript, java, python
Published: 2021-06-14 07:50:57

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/maximum-units-on-a-truck/discuss/1271374).*

---

#### [Leetcode Problem #1710 (*Easy*): Maximum Units on a Truck](https://leetcode.com/problems/maximum-units-on-a-truck/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
You are assigned to put some amount of boxes onto **one truck**. You are given a 2D array `boxTypes`, where `boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]`:
  -  `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_.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output:| 8
Explanation:| There are:<br><br>- 1 box of the first type that contains 3 units.<br>- 2 boxes of the second type that contain 2 units each.<br>- 3 boxes of the third type that contain 1 unit each.<br><br>You can take all the boxes of the first and second types, and one box of the third type.<br><br>The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
>
Example 2:||
|---:|---|
Input:| boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output:| 91

---

#### ***Constraints:***
>
 - `1 <= boxTypes.length <= 1000`
 - `1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000`
 - `1 <= truckSize <= 10^6`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

For this problem, we simply need to prioritize the more valuable boxes first. To do this, we should **sort** the boxtypes array (**B**) in descending order by the number of units per box (**B[i][1]**).

Then we can iterate through **B** and at each step, we should add as many of the **boxes** as we can, until we reach the truck size (**T**). We should add the number of **boxes** added multiplied by the units per box to our answer (**ans**), and decrease **T** by the same number of **boxes**.

Once the truck is full (**T == 0**), or once the iteration is done, we should **return ans**.

 - _**Time Complexity: O(N log N)** where **N** is the length of **B**, for the sort_
 - _**Space Complexity: O(1)**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var maximumUnits = function(B, T) {
    B.sort((a,b) => b[1] - a[1])
    let ans = 0
    for (let i = 0; T && i < B.length; i++) {
        let count = Math.min(B[i][0], T)
        ans += count * B[i][1], T -= count
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def maximumUnits(self, B: List[List[int]], T: int) -> int:
        B.sort(key=lambda x: x[1], reverse=True)
        ans = 0
        for b,n in B:
            boxes = min(b, T)
            ans += boxes * n
            T -= boxes
            if T == 0: return ans
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int maximumUnits(int[][] B, int T) {
        Arrays.sort(B, (a,b) -> b[1] - a[1]);
        int ans = 0;
        for (int[] b : B) {
            int count = Math.min(b[0], T);
            ans += count * b[1];
            T -= count;
            if (T == 0) return ans;
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int maximumUnits(vector<vector<int>>& B, int T) {
        sort(B.begin(), B.end(), [](auto& a, auto& b) { return b[1] < a[1];});
        int ans = 0;
        for (auto& b : B) {
            int count = min(b[0], T);
            ans += count * b[1], T -= count;
            if (!T) return ans;
        }
        return ans;
    }
};
```