This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1710 (Easy): Maximum Units on a Truck
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
You are assigned to put some amount of boxes onto one truck. You are given a 2D array
boxTypes, whereboxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxes iis the number of boxes of typei.numberOfUnitsPerBox iis the number of units in each box of the typei.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 exceedtruckSize.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:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
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 <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 10^6
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
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:
(Jump to: Problem Description || Solution Idea)
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:
(Jump to: Problem Description || Solution Idea)
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:
(Jump to: Problem Description || Solution Idea)
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;
}
return ans;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
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;
}
return ans;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-06-14T07:50:57+00:00) Solution: Maximum Units on a Truck. Retrieved from https://www.scien.cx/2021/06/14/solution-maximum-units-on-a-truck/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.