{"id":7889,"date":"2021-01-02T23:11:37","date_gmt":"2021-01-03T07:11:37","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7889"},"modified":"2021-01-02T23:12:06","modified_gmt":"2021-01-03T07:12:06","slug":"leetcode-1710-maximum-units-on-a-truck","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1710-maximum-units-on-a-truck\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1710. Maximum Units on a Truck"},"content":{"rendered":"\n<p>You are assigned to put some amount of boxes onto&nbsp;<strong>one truck<\/strong>. You are given a 2D array&nbsp;<code>boxTypes<\/code>, where&nbsp;<code>boxTypes[i] = [numberOfBoxes<sub>i<\/sub>, numberOfUnitsPerBox<sub>i<\/sub>]<\/code>:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>numberOfBoxes<sub>i<\/sub><\/code>&nbsp;is the number of boxes of type&nbsp;<code>i<\/code>.<\/li><li><code>numberOfUnitsPerBox<sub>i<\/sub><\/code>is the number of units in each box of the type&nbsp;<code>i<\/code>.<\/li><\/ul>\n\n\n\n<p>You are also given an integer&nbsp;<code>truckSize<\/code>, which is the&nbsp;<strong>maximum<\/strong>&nbsp;number of&nbsp;<strong>boxes<\/strong>&nbsp;that can be put on the truck. You can choose any boxes to put on the truck as long as the number&nbsp;of boxes does not exceed&nbsp;<code>truckSize<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>maximum<\/strong>&nbsp;total number of&nbsp;<strong>units<\/strong>&nbsp;that can be put on the truck.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> There are:\n- 1 box of the first type that contains 3 units.\n- 2 boxes of the second type that contain 2 units each.\n- 3 boxes of the third type that contain 1 unit each.\nYou can take all the boxes of the first and second types, and one box of the third type.\nThe total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10\n<strong>Output:<\/strong> 91\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= boxTypes.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= numberOfBoxes<sub>i<\/sub>, numberOfUnitsPerBox<sub>i<\/sub>&nbsp;&lt;= 1000<\/code><\/li><li><code>1 &lt;= truckSize &lt;= 10<sup>6<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Sort by unit in descending order.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {\n    sort(begin(boxTypes), end(boxTypes), [](const auto& a, const auto& b){\n      return a[1] > b[1]; \/\/ Sort by unit DESC\n    });\n    \n    int ans = 0;\n    for (const auto& b : boxTypes) {      \n      ans += b[1] * min(b[0], truckSize);      \n      if ((truckSize -= b[0]) <= 0) break;      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are assigned to put some amount of boxes onto&nbsp;one truck. You are given a 2D array&nbsp;boxTypes, where&nbsp;boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]: numberOfBoxesi&nbsp;is the number of&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[222,88,23],"class_list":["post-7889","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-easy","tag-greedy","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7889","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7889"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7889\/revisions"}],"predecessor-version":[{"id":7891,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7889\/revisions\/7891"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7889"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7889"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7889"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}