#1889
Minimum Space Wasted From Packaging
master · 1890 · lc hard +32 · verified · 33.5% accepted · 423 likes · top 11%
Description
You have n packages to ship; the i-th has size packages[i]. There are m suppliers, each offering boxes of certain sizes. A package of size p requires a box of size >= p; the wasted space is (box size - p).
Choose one supplier and assign each package to a box from that supplier to minimize total wasted space. Return the minimum wasted space modulo 109 + 7, or -1 if no supplier can accommodate all packages.
Example 1:
Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.
Example 2:
Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.
Example 3:
Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.
Code
1
2
3