Welcome to Subscribe On Youtube
1889. Minimum Space Wasted From Packaging
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 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 109 + 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 <= 1051 <= m <= 1051 <= packages[i] <= 1051 <= boxes[j].length <= 1051 <= boxes[j][k] <= 105sum(boxes[j].length) <= 105- The elements in
boxes[j]are distinct.
Solutions
-
class Solution { public int minWastedSpace(int[] packages, int[][] boxes) { int n = packages.length; final long inf = 1L << 62; Arrays.sort(packages); long ans = inf; for (var box : boxes) { Arrays.sort(box); if (packages[n - 1] > box[box.length - 1]) { continue; } long s = 0; int i = 0; for (int b : box) { int j = search(packages, b, i); s += 1L * (j - i) * b; i = j; } ans = Math.min(ans, s); } if (ans == inf) { return -1; } long s = 0; for (int p : packages) { s += p; } final int mod = (int) 1e9 + 7; return (int) ((ans - s) % mod); } private int search(int[] nums, int x, int l) { int r = nums.length; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] > x) { r = mid; } else { l = mid + 1; } } return l; } } -
class Solution { public: int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) { int n = packages.size(), m = boxes.size(); sort(packages.begin(), packages.end()); const int mod = 1e9 + 7; const long long inf = 1LL << 62; long long ans = inf; for (auto& box : boxes) { sort(box.begin(), box.end()); if (packages.back() > box.back()) { continue; } int i = 0; long long s = 0; for (auto& b : box) { int j = upper_bound(packages.begin() + i, packages.end(), b) - packages.begin(); s += 1LL * (j - i) * b; i = j; } ans = min(ans, s); } return ans == inf ? -1 : (ans - accumulate(packages.begin(), packages.end(), 0LL)) % mod; } }; -
class Solution: def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int: mod = 10**9 + 7 ans = inf packages.sort() for box in boxes: box.sort() if packages[-1] > box[-1]: continue s = i = 0 for b in box: j = bisect_right(packages, b, lo=i) s += (j - i) * b i = j ans = min(ans, s) if ans == inf: return -1 return (ans - sum(packages)) % mod -
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 } -
function minWastedSpace(packages: number[], boxes: number[][]): number { const n = packages.length; const inf = Infinity; packages.sort((a, b) => a - b); let ans = inf; for (const box of boxes) { box.sort((a, b) => a - b); if (packages[n - 1] > box[box.length - 1]) { continue; } let s = 0; let i = 0; for (const b of box) { const j = search(packages, b, i); s += (j - i) * b; i = j; } ans = Math.min(ans, s); } if (ans === inf) { return -1; } const s = packages.reduce((a, b) => a + b, 0); return (ans - s) % 1000000007; } function search(nums: number[], x: number, l: number): number { let r = nums.length; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] > x) { r = mid; } else { l = mid + 1; } } return l; }