You are given an array packages where packages[i] is the size of the i-th package you need to ship. You are also given a 2D array boxes, where boxes[j] is a list of available box sizes from supplier j. Each supplier can only be used once, and you must pick all boxes you use from a single supplier (i.e., you cannot mix boxes from different suppliers). You can use any number of boxes from the chosen supplier, and you may reuse box sizes as many times as needed.
Your task is to select a supplier and pack each package into a box from that supplier (each package in its own box, and the box must fit the package). The wasted space is the total space left unused in all boxes (i.e., for each package, the difference between the box size used and the package size).
Return the minimum total space wasted across all suppliers. If it is impossible to pack all packages using any single supplier, return -1.
At first glance, the problem appears to involve matching each package to the closest fitting box from a supplier. If we try a brute-force approach, we would check every supplier and, for each, try all possible box assignments for every package. However, this quickly becomes infeasible as the number of packages and box sizes grows.
The key insight is that for any supplier, to minimize wasted space, each package should be placed in the smallest box from that supplier that fits it. This is a classic best fit problem. We can sort both packages and the supplier's boxes to efficiently find, for each package, the smallest box that fits.
Since we must use boxes from only one supplier, we repeat this process for each supplier and take the minimum total wasted space among all suppliers. If there is any package that cannot be packed by a supplier (i.e., is larger than all their box sizes), that supplier is skipped.
packages array in ascending order. This allows us to process packages from smallest to largest.boxes:
-1. Otherwise, return the minimum wasted space modulo 10^9 + 7 (as per Leetcode's constraints).We use sorting and binary search to efficiently match packages to boxes. Prefix sums can be used to quickly compute the total size of packages assigned to each box size.
Suppose packages = [2, 3, 5] and boxes = [[4, 8], [2, 8]].
[4, 8]):
[2, 3, 5][4, 8][2, 8]):
[2, 8]n packages and m box sizes, this can be O(m^n), which is infeasible for large inputs.
packages: O(n \log n)s suppliers), sorting their boxes: O(m \log m)O(n \log m) (using binary search for each package)O(n \log n + s \cdot (m \log m + n \log m))O(n + m) for sorting and prefix sums.The optimized method is efficient enough for Leetcode constraints.
The problem asks us to minimize the wasted space when packing packages using boxes from a single supplier. The optimal approach is to, for each supplier, sort their box sizes and the packages, and for each package, pick the smallest available box that fits. We repeat this for all suppliers and select the minimum total wasted space. Sorting and binary search make the solution efficient. The elegance comes from realizing that for each supplier, the best fit for each package is always the smallest possible box that fits, and that the process can be efficiently repeated for all suppliers.
from bisect import bisect_right
from typing import List
class Solution:
def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
MOD = 10 ** 9 + 7
packages.sort()
n = len(packages)
prefix = [0]
for p in packages:
prefix.append(prefix[-1] + p)
res = float('inf')
for supplier in boxes:
supplier.sort()
if supplier[-1] < packages[-1]:
continue
waste = 0
prev = 0
for b in supplier:
idx = bisect_right(packages, b, prev)
waste += b * (idx - prev) - (prefix[idx] - prefix[prev])
prev = idx
if prev == n:
res = min(res, waste)
return res % MOD if res != float('inf') else -1
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class Solution {
public:
int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
const int MOD = 1e9 + 7;
sort(packages.begin(), packages.end());
int n = packages.size();
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + packages[i];
long long res = LLONG_MAX;
for (auto& supplier : boxes) {
sort(supplier.begin(), supplier.end());
if (supplier.back() < packages.back()) continue;
long long waste = 0;
int prev = 0;
for (int b : supplier) {
int idx = upper_bound(packages.begin() + prev, packages.end(), b) - packages.begin();
waste += (long long)(b) * (idx - prev) - (prefix[idx] - prefix[prev]);
prev = idx;
}
if (prev == n)
res = min(res, waste);
}
return res == LLONG_MAX ? -1 : res % MOD;
}
};
import java.util.*;
class Solution {
public int minWastedSpace(int[] packages, int[][] boxes) {
int MOD = 1_000_000_007;
Arrays.sort(packages);
int n = packages.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + packages[i];
long res = Long.MAX_VALUE;
for (int[] supplier : boxes) {
Arrays.sort(supplier);
if (supplier[supplier.length - 1] < packages[n - 1]) continue;
long waste = 0;
int prev = 0;
for (int b : supplier) {
int idx = upperBound(packages, b, prev);
waste += (long)(b) * (idx - prev) - (prefix[idx] - prefix[prev]);
prev = idx;
}
if (prev == n)
res = Math.min(res, waste);
}
return res == Long.MAX_VALUE ? -1 : (int)(res % MOD);
}
private int upperBound(int[] arr, int target, int start) {
int l = start, r = arr.length;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] <= target) l = m + 1;
else r = m;
}
return l;
}
}
/**
* @param {number[]} packages
* @param {number[][]} boxes
* @return {number}
*/
var minWastedSpace = function(packages, boxes) {
const MOD = 1e9 + 7;
packages.sort((a, b) => a - b);
const n = packages.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + packages[i];
let res = Number.MAX_SAFE_INTEGER;
for (const supplier of boxes) {
supplier.sort((a, b) => a - b);
if (supplier[supplier.length - 1] < packages[n - 1]) continue;
let waste = 0;
let prev = 0;
for (const b of supplier) {
let idx = upperBound(packages, b, prev);
waste += b * (idx - prev) - (prefix[idx] - prefix[prev]);
prev = idx;
}
if (prev === n)
res = Math.min(res, waste);
}
return res === Number.MAX_SAFE_INTEGER ? -1 : res % MOD;
};
function upperBound(arr, target, start) {
let l = start, r = arr.length;
while (l < r) {
let m = l + ((r - l) >> 1);
if (arr[m] <= target) l = m + 1;
else r = m;
}
return l;
}