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 i-th package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the j-th 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 size-2and size-3into two boxes of size-4and the package with size-5into a box of size-8. This would result in a waste of(4-2) + (4-3) + (8-5) = 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 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.
Constraints:
n == packages.lengthm == boxes.length1 <= n <= 10^51 <= m <= 10^51 <= packages[i] <= 10^51 <= boxes[j].length <= 10^51 <= boxes[j][k] <= 10^5sum(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; } } ############ class Solution { public int minWastedSpace(int[] packages, int[][] boxes) { int n = packages.length; Arrays.sort(packages); long[] preSum = new long[n + 1]; for (int i = 0; i < n; ++i) { preSum[i + 1] = preSum[i] + packages[i]; } long res = Long.MAX_VALUE; for (int[] box : boxes) { Arrays.sort(box); if (packages[n - 1] > box[box.length - 1]) { continue; } long t = 0; int low = 0; for (int b : box) { int idx = searchRight(packages, b, low); t += ((idx - low) * (long) b - (preSum[idx] - preSum[low])); low = idx; } res = Math.min(res, t); } return res == Long.MAX_VALUE ? -1 : (int) (res % 1000000007); } private int searchRight(int[] packages, int target, int low) { int high = packages.length; while (low < high) { int mid = (low + high) >> 1; if (packages[mid] <= target) { low = mid + 1; } else { high = mid; } } return low; } } -
// OJ: https://leetcode.com/problems/minimum-space-wasted-from-packaging/ // 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/minimum-space-wasted-from-packaging/ 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 -
function minWastedSpace(packages: number[], boxes: number[][]): number { const MOD = 10 ** 9 + 7; packages.sort((a, b) => a - b); const max_package = packages[packages.length - 1]; const total = packages.reduce((a, c) => a + c, 0); let res = Infinity; for (let box of boxes) { box.sort((a, b) => a - b); if (max_package > box[box.length - 1]) continue; let left = 0, sum = 0; for (let capacity of box) { let right = searchRight(packages, capacity, left); sum += (right - left) * capacity; left = right; } res = Math.min(res, sum); } return res == Infinity ? -1 : (res - total) % MOD; } function searchRight(packages: number[], target: number, left: number): number { let right = packages.length; while (left < right) { let mid = (left + right) >> 1; if (packages[mid] <= target) { left = mid + 1; } else { right = mid; } } return left; } -
func minWastedSpace(packages []int, boxes [][]int) int { n := len(packages) inf := 1 << 62 sort.Ints(packages) ans := inf for _, box := range boxes { sort.Ints(box) if packages[n-1] > box[len(box)-1] { continue } s, i := 0, 0 for _, b := range box { j := sort.SearchInts(packages[i:], b+1) + i s += (j - i) * b i = j } ans = min(ans, s) } if ans == inf { return -1 } s := 0 for _, p := range packages { s += p } const mod = 1e9 + 7 return (ans - s) % mod } func min(a, b int) int { if a < b { return a } return b }