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-2 and size-3 into two boxes of size-4 and the package with size-5 into 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#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| 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;
}
|
