New Problem Solution -"1710. Maximum Units on a Truck"

haoel · haoel · commit 06eab70b922d · 2021-03-30T18:48:17.000+08:00
diff --git a/README.md b/README.md
@@ -63,6 +63,7 @@ LeetCode
 |1725|[Number Of Rectangles That Can Form The Largest Square](https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/) | [C++](./algorithms/cpp/numberOfRectanglesThatCanFormTheLargestSquare/NumberOfRectanglesThatCanFormTheLargestSquare.cpp)|Easy|
 |1717|[Maximum Score From Removing Substrings](https://leetcode.com/problems/maximum-score-from-removing-substrings/) | [C++](./algorithms/cpp/maximumScoreFromRemovingSubstrings/MaximumScoreFromRemovingSubstrings.cpp)|Medium|
 |1716|[Calculate Money in Leetcode Bank](https://leetcode.com/problems/calculate-money-in-leetcode-bank/) | [C++](./algorithms/cpp/calculateMoneyInLeetcodeBank/CalculateMoneyInLeetcodeBank.cpp)|Easy|
+|1710|[Maximum Units on a Truck](https://leetcode.com/problems/maximum-units-on-a-truck/) | [C++](./algorithms/cpp/maximumUnitsOnATruck/MaximumUnitsOnATruck.cpp)|Easy|
 |1625|[Lexicographically Smallest String After Applying Operations](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/) | [C++](./algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp)|Medium|
 |1624|[Largest Substring Between Two Equal Characters](https://leetcode.com/problems/largest-substring-between-two-equal-characters/) | [C++](./algorithms/cpp/largestSubstringBetweenTwoEqualCharacters/LargestSubstringBetweenTwoEqualCharacters.cpp)|Easy|
 |1605|[Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/) | [C++](./algorithms/cpp/FindValidMatrixGivenRowAndColumnSums/FindValidMatrixGivenRowAndColumnSums.cpp)|Medium|
diff --git a/algorithms/cpp/maximumUnitsOnATruck/MaximumUnitsOnATruck.cpp b/algorithms/cpp/maximumUnitsOnATruck/MaximumUnitsOnATruck.cpp
@@ -0,0 +1,69 @@
+// Source : https://leetcode.com/problems/maximum-units-on-a-truck/
+// Author : Hao Chen
+// Date   : 2021-03-30
+
+/***************************************************************************************************** 
+ *
+ * You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, 
+ * where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
+ * 
+ * 	numberOfBoxesi is the number of boxes of type i.
+ * 	numberOfUnitsPerBoxi 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.
+ * 
+ * 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 <= 1000
+ * 	1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
+ * 	1 <= truckSize <= 10^6
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    void print(vector<vector<int>>& boxes) {
+        cout << "{ ";
+        for(int i=0; i<boxes.size()-1; i++){
+            cout << "[" << boxes[i][0] << ","<< boxes[i][1] << "], ";
+        }
+        int i=boxes.size()-1;
+        cout << "[" << boxes[i][0] << ", "<< boxes[i][1] << "] } "<< endl;
+    }
+public:
+    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
+        sort(boxTypes.begin(), boxTypes.end(), 
+             [&](vector<int>& lhs, vector<int>& rhs){return lhs[1] > rhs[1]; });
+        //print(boxTypes);
+        int units = 0;
+        for(auto& box : boxTypes) {
+            if (truckSize >= box[0]) {
+                units += box[0] * box[1];
+            }else{
+                units += truckSize * box[1];
+            }
+            truckSize -= box[0];
+            if (truckSize <= 0 ) break;
+        }
+        return units;
+    }
+};
