Hard
题目描述
你有 n 个包裹要装入盒子中，每个包裹装入一个盒子。有 m 个供应商，每个供应商都能生产不同尺寸的盒子（供应量无限）。如果包裹的尺寸小于或等于盒子的尺寸，那么这个包裹就可以装入这个盒子。
包裹尺寸用一个整数数组 packages 表示，其中 packages[i] 是第 i 个包裹的尺寸。供应商用二维整数数组 boxes 表示，其中 boxes[j] 是第 j 个供应商能够提供的盒子尺寸数组。
你需要选择一个供应商并使用他们的盒子，使得总浪费空间最小化。对于每个装在盒子里的包裹，我们定义浪费的空间等于 盒子的尺寸 - 包裹的尺寸。总浪费空间为所有盒子中浪费空间的总和。
例如，如果你需要装入尺寸为 [2,3,5] 的包裹，供应商提供尺寸为 [4,8] 的盒子，你可以将尺寸为 2 和 3 的包裹装入两个尺寸为 4 的盒子，将尺寸为 5 的包裹装入一个尺寸为 8 的盒子。这样的浪费为 (4-2) + (4-3) + (8-5) = 6。
返回通过最优选择盒子供应商得到的最小总浪费空间，如果无法将所有包裹装入盒子则返回 -1。由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。
示例 1:
输入：packages = [2,3,5], boxes = [[4,8],[2,8]]
输出：6
解释：选择第一个供应商最优，使用两个尺寸为 4 的盒子和一个尺寸为 8 的盒子。
总浪费为 (4-2) + (4-3) + (8-5) = 6。
示例 2:
输入：packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
输出：-1
解释：没有盒子能装入尺寸为 5 的包裹。
示例 3:
输入：packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
输出：9
约束条件:
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^5boxes[j]中的元素互不相同
解题思路
这是一个典型的贪心算法结合二分查找的问题。核心思路是对每个供应商计算最小浪费空间，然后取全局最小值。
算法分析:
预处理阶段：对包裹数组排序，计算前缀和。排序后可以使用二分查找快速定位包裹范围，前缀和可以快速计算包裹尺寸总和。
对每个供应商：
- 首先检查该供应商是否能装下所有包裹（最大盒子尺寸 >= 最大包裹尺寸）
- 对供应商的盒子尺寸排序，然后贪心分配
贪心策略：对于排序后的盒子，每个盒子应该装入所有能装下的最大包裹。具体来说，对于当前盒子尺寸
boxSize，找到所有尺寸 <=boxSize且还未分配的包裹，将它们都装入这个尺寸的盒子。二分查找优化：使用二分查找快速找到每个盒子能装下的包裹范围，避免线性扫描。
前缀和优化：使用前缀和快速计算包裹尺寸总和，避免重复计算。
时间复杂度分析：
- 排序包裹：O(n log n)
- 对每个供应商排序盒子：O(总盒子数 × log(平均盒子数))
- 二分查找：O(总盒子数 × log n)
- 总体：O(n log n + 总盒子数 × log n)
这种方法能有效处理大规模数据，是该问题的最优解法。
代码实现
class Solution {
public:
int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
const int MOD = 1e9 + 7;
int n = packages.size();
// 排序包裹并计算前缀和
sort(packages.begin(), packages.end());
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + packages[i];
}
long long minWaste = LLONG_MAX;
for (auto& box : boxes) {
sort(box.begin(), box.end());
// 检查最大盒子是否能装下最大包裹
if (box.back() < packages.back()) continue;
long long waste = 0;
int left = 0;
for (int boxSize : box) {
// 使用二分查找找到第一个大于boxSize的包裹位置
int right = upper_bound(packages.begin(), packages.end(), boxSize) - packages.begin();
if (right > left) {
// 计算[left, right)范围内的包裹数量和总尺寸
int count = right - left;
long long totalSize = prefix[right] - prefix[left];
waste += (long long)count * boxSize - totalSize;
left = right;
}
}
minWaste = min(minWaste, waste);
}
return minWaste == LLONG_MAX ? -1 : minWaste % MOD;
}
};
class Solution:
def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
MOD = 10**9 + 7
n = len(packages)
# 排序包裹并计算前缀和
packages.sort()
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + packages[i]
min_waste = float('inf')
for box in boxes:
box.sort()
# 检查最大盒子是否能装下最大包裹
if box[-1] < packages[-1]:
continue
waste = 0
left = 0
for box_size in box:
# 使用二分查找找到第一个大于box_size的包裹位置
right = bisect.bisect_right(packages, box_size)
if right > left:
# 计算[left, right)范围内的包裹数量和总尺寸
count = right - left
total_size = prefix[right] - prefix[left]
waste += count * box_size - total_size
left = right
min_waste = min(min_waste, waste)
return -1 if min_waste == float('inf') else min_waste % MOD
public class Solution {
public int MinWastedSpace(int[] packages, int[][] boxes) {
const int MOD = 1000000007;
int n = packages.Length;
// 排序包裹并计算前缀和
Array.Sort(packages);
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + packages[i];
}
long minWaste = long.MaxValue;
foreach (var box in boxes) {
Array.Sort(box);
// 检查最大盒子是否能装下最大包裹
if (box[box.Length - 1] < packages[n - 1]) continue;
long waste = 0;
int left = 0;
foreach (int boxSize in box) {
// 使用二分查找找到第一个大于boxSize的包裹位置
int right = Array.BinarySearch(packages, left, n - left, boxSize);
if (right < 0) {
right = ~right;
} else {
// 找到最后一个等于boxSize的位置
while (right < n && packages[right] == boxSize) {
right++;
}
}
if (right > left) {
// 计算[left, right)范围内的包裹数量和总尺寸
int count = right - left;
long totalSize = prefix[right] - prefix[left];
waste += (long)count * boxSize - totalSize;
left = right;
}
}
minWaste = Math.Min(minWaste, waste);
}
return minWaste == long.MaxValue ? -1 : (int)(minWaste % MOD);
}
}
var minWastedSpace = function(packages, boxes) {
const MOD = 1000000007;
packages.sort((a, b) => a - b);
const totalPackages = packages.reduce((sum, p) => sum + p, 0);
let minWaste = Infinity;
for (let supplier of boxes) {
supplier.sort((a, b) => a - b);
// Check if this supplier can handle all packages
if (supplier[supplier.length - 1] < packages[packages.length - 1]) {
continue;
}
let waste = 0;
let packageIndex = 0;
for (let boxSize of supplier) {
let count = 0;
// Find how many packages can fit in this box size
while (packageIndex < packages.length && packages[packageIndex] <= boxSize) {
packageIndex++;
count++;
}
waste += boxSize * count;
if (packageIndex === packages.length) break;
}
waste = (waste - totalPackages) % MOD;
minWaste = Math.min(minWaste, waste);
}
return minWaste === Infinity ? -1 : minWaste;
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(n log n + S log n) |
| 空间复杂度 | O(n) |
其中 n 是包裹数量，S 是所有供应商的盒子总数。