{"id":8546,"date":"2021-08-09T19:14:55","date_gmt":"2021-08-10T02:14:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8546"},"modified":"2021-08-09T19:16:22","modified_gmt":"2021-08-10T02:16:22","slug":"leetcode-1889-minimum-space-wasted-from-packaging","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1889-minimum-space-wasted-from-packaging\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1889. Minimum Space Wasted From Packaging"},"content":{"rendered":"\n<p>You have&nbsp;<code>n<\/code>&nbsp;packages that you are trying to place in boxes,&nbsp;<strong>one package in each box<\/strong>. There are&nbsp;<code>m<\/code>&nbsp;suppliers that each produce boxes of&nbsp;<strong>different sizes<\/strong>&nbsp;(with infinite supply). A package can be placed in a box if the size of the package is&nbsp;<strong>less than or equal to<\/strong>&nbsp;the size of the box.<\/p>\n\n\n\n<p>The package sizes are given as an integer array&nbsp;<code>packages<\/code>, where&nbsp;<code>packages[i]<\/code>&nbsp;is the&nbsp;<strong>size<\/strong>&nbsp;of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;package. The suppliers are given as a 2D integer array&nbsp;<code>boxes<\/code>, where&nbsp;<code>boxes[j]<\/code>&nbsp;is an array of&nbsp;<strong>box sizes<\/strong>&nbsp;that the&nbsp;<code>j<sup>th<\/sup><\/code>&nbsp;supplier produces.<\/p>\n\n\n\n<p>You want to choose a&nbsp;<strong>single supplier<\/strong>&nbsp;and use boxes from them such that the&nbsp;<strong>total wasted space&nbsp;<\/strong>is&nbsp;<strong>minimized<\/strong>. For each package in a box, we define the space&nbsp;<strong>wasted<\/strong>&nbsp;to be&nbsp;<code>size of the box - size of the package<\/code>. The&nbsp;<strong>total wasted space<\/strong>&nbsp;is the sum of the space wasted in&nbsp;<strong>all<\/strong>&nbsp;the boxes.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if you have to fit packages with sizes&nbsp;<code>[2,3,5]<\/code>&nbsp;and the supplier offers boxes of sizes&nbsp;<code>[4,8]<\/code>, you can fit the packages of size-<code>2<\/code>&nbsp;and size-<code>3<\/code>&nbsp;into two boxes of size-<code>4<\/code>&nbsp;and the package with size-<code>5<\/code>&nbsp;into a box of size-<code>8<\/code>. This would result in a waste of&nbsp;<code>(4-2) + (4-3) + (8-5) = 6<\/code>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum total wasted space<\/strong>&nbsp;by choosing the box supplier&nbsp;<strong>optimally<\/strong>, or&nbsp;<\/em><code>-1<\/code>&nbsp;<em>if it is&nbsp;<strong>impossible<\/strong>&nbsp;to fit all the packages inside boxes.&nbsp;<\/em>Since the answer may be&nbsp;<strong>large<\/strong>, return it&nbsp;<strong>modulo&nbsp;<\/strong><code>10<sup>9<\/sup>&nbsp;+ 7<\/code>.<\/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> packages = [2,3,5], boxes = [[4,8],[2,8]]\n<strong>Output:<\/strong> 6\n<strong>Explanation<\/strong>: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.\nThe total waste is (4-2) + (4-3) + (8-5) = 6.\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> packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> There is no box that the package of size 5 can fit in.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]\n<strong>Output:<\/strong> 9\n<strong>Explanation:<\/strong> It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.\nThe total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == packages.length<\/code><\/li><li><code>m == boxes.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= m &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= packages[i] &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= boxes[j].length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= boxes[j][k] &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>sum(boxes[j].length) &lt;= 10<sup>5<\/sup><\/code><\/li><li>The elements in&nbsp;<code>boxes[j]<\/code>&nbsp;are&nbsp;<strong>distinct<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy + Binary Search<\/strong><\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>sort packages and boxes<\/li><li>for each box find all (unpacked) packages that are smaller or equal to itself.<\/li><\/ol>\n\n\n\n<p>Time complexity: O(nlogn) + O(mlogm) + O(mlogn)<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 minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {\n    constexpr int kMod = 1e9 + 7;\n    const int n = packages.size();        \n    sort(begin(packages), end(packages));    \n    const auto bit = begin(packages);\n    const auto eit = end(packages);\n    long sum = accumulate(bit, eit, 0L);\n    long ans = LLONG_MAX;\n    for (auto& box : boxes) {\n      sort(begin(box), end(box));\n      int l = 0;\n      long cur = 0;\n      for (long b : box) {\n        int r = upper_bound(bit + l, eit, b) - bit;\n        cur += b * (r - l);\n        if (r == n) {\n          ans = min(ans, cur - sum);\n          break;\n        }\n        l = r;\n      }      \n    }\n    return ans == LLONG_MAX ? -1 : ans % kMod;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have&nbsp;n&nbsp;packages that you are trying to place in boxes,&nbsp;one package in each box. There are&nbsp;m&nbsp;suppliers that each produce boxes of&nbsp;different sizes&nbsp;(with infinite supply). A&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,88,217],"class_list":["post-8546","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-greedy","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8546","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=8546"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8546\/revisions"}],"predecessor-version":[{"id":8548,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8546\/revisions\/8548"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8546"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8546"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8546"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}