Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1889.html
1889. Minimum Space Wasted From Packaging
Level
Hard
Description
You have n
packages that you are trying to place in boxes, one package in each box. There are m
suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.
The package sizes are given as an integer array packages
, where packages[i]
is the size of the ith
package. The suppliers are given as a 2D integer array boxes
, where boxes[j]
is an array of box sizes that the jth
supplier produces.
You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box  size of the package
. The total wasted space is the sum of the space wasted in all the boxes.
 For example, if you have to fit packages with sizes
[2,3,5]
and the supplier offers boxes of sizes[4,8]
, you can fit the packages of size2
and size3
into two boxes of size4
and the package with size5
into a box of size8
. This would result in a waste of(42) + (43) + (85) = 6
.
Return the minimum total wasted space by choosing the box supplier optimally, or 1
if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 10^9 + 7
.
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 size4 boxes and one size8 box.
The total waste is (42) + (43) + (85) = 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 size5 boxes, two size10 boxes, and two size14 boxes. The total waste is (53) + (55) + (108) + (1010) + (1411) + (1412) = 9.
Constraints:
n == packages.length
m == boxes.length
1 <= n <= 10^5
1 <= m <= 10^5
1 <= packages[i] <= 10^5
1 <= boxes[j].length <= 10^5
1 <= boxes[j][k] <= 10^5
sum(boxes[j].length) <= 10^5
 The elements in
boxes[j]
are distinct.
Solution
Obviously, each package should be placed in the box such that the size of the box is at least the size of the package and the size of the box should be as small as possible.
Sort packages
and each row of boxes
. Then calculate the prefix sums of packages
. For each row of boxes
, if the size of the largest box is still less than the size of the largest box, then the row is not available, so continue. Otherwise, for each box, use binary search to find the maximum package size that can be placed in the box, and calculate the wasted space. When all boxes in a row of boxes
are looped over, the total wasted space can be calculated.
After all rows of boxes
are looped over, the minimum wasted space can be calculated.

class Solution { public int minWastedSpace(int[] packages, int[][] boxes) { final int MODULO = 1000000007; int n = packages.length, m = boxes.length; Arrays.sort(packages); for (int i = 0; i < m; i++) Arrays.sort(boxes[i]); long[] packagesPrefixSum = new long[n]; packagesPrefixSum[0] = packages[0]; for (int i = 1; i < n; i++) packagesPrefixSum[i] = packagesPrefixSum[i  1] + packages[i]; long minWasted = Long.MAX_VALUE; int maxPackage = packages[n  1], minPackage = packages[0]; for (int[] curBoxes : boxes) { int count = curBoxes.length; if (curBoxes[count  1] < maxPackage) continue; int last = 1; long totalWasted = 0; for (int i = 0; i < count; i++) { int box = curBoxes[i]; if (box < minPackage) continue; int index = lastIndex(packages, box); long totalSpace = packagesPrefixSum[index]  (last < 0 ? 0 : packagesPrefixSum[last]); long wastedSpace = (long) (index  last) * box  totalSpace; totalWasted += wastedSpace; last = index; } minWasted = Math.min(minWasted, totalWasted); } return minWasted == Long.MAX_VALUE ? 1 : (int) (minWasted % MODULO); } public int lastIndex(int[] arr, int target) { int low = 0, high = arr.length  1; while (low < high) { int mid = (high  low + 1) / 2 + low; if (arr[mid] <= target) low = mid; else high = mid  1; } return low; } }

// OJ: https://leetcode.com/problems/minimumspacewastedfrompackaging/ // Time: O(PlogP + BlogB) // Space: O(max(P)) class Solution { public: int minWastedSpace(vector<int>& P, vector<vector<int>>& B) { long mod = 1e9 + 7, ans = LONG_MAX, N = P.size(), sum[100001] = {}, cnt[100001] = {}; sort(begin(P), end(P)); for (int i = 1, j = 0; i < 100001; ++i) { sum[i] = sum[i  1]; cnt[i] = cnt[i  1]; while (j < N && P[j] == i) { sum[i] += i; cnt[i]++; ++j; } } for (auto &b : B) { sort(begin(b), end(b)); if (b.back() < P.back()) continue; long tmp = 0, prev = 0; for (int i = 0; i < b.size(); ++i) { tmp += (cnt[b[i]]  cnt[prev]) * b[i]  (sum[b[i]]  sum[prev]); prev = b[i]; } ans = min(ans, tmp); } return ans == LONG_MAX ? 1 : ans % mod; } };

class Solution: def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) > int: packages.sort() res = inf for box in boxes: box.sort() if packages[1] > box[1]: continue t = last = 0 for b in box: idx = bisect_right(packages, b, lo=last) t += (idx  last) * b last = idx res = min(res, t) return 1 if res == inf else (res  sum(packages)) % (10**9 + 7) ############ # 1889. Minimum Space Wasted From Packaging # https://leetcode.com/problems/minimumspacewastedfrompackaging/ class Solution: def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) > int: M = 10 ** 9 + 7 res = float('inf') packages.sort() ss = sum(packages) for box in boxes: curr = last = 0 for b in sorted(box): index = bisect.bisect(packages, b) curr += b * (index  last) last = index if last == len(packages): res = min(res, curr  ss) return 1 if res == float('inf') else res % M