1889-装包裹的最小浪费空间

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

给你 n 个包裹，你需要把它们装在箱子里， 每个箱子装一个包裹 。总共有 m 个供应商提供 不同尺寸
的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 小于等于 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。

包裹的尺寸用一个整数数组 packages 表示，其中 packages[i] 是第 i 个包裹的尺寸。供应商用二维数组 boxes
表示，其中 boxes[j] 是第 j 个供应商提供的所有箱子尺寸的数组。

你想要选择 一个供应商 并只使用该供应商提供的箱子，使得 总浪费空间最小 。对于每个装了包裹的箱子，我们定义 浪费的 空间等于
箱子的尺寸 - 包裹的尺寸 。 总浪费空间 为 所有 箱子中浪费空间的总和。

  • 比方说，如果你想要用尺寸数组为 [4,8] 的箱子装下尺寸为 [2,3,5] 的包裹，你可以将尺寸为 2 和 3 的两个包裹装入两个尺寸为 4 的箱子中，同时把尺寸为 5 的包裹装入尺寸为 8 的箱子中。总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

请你选择 最优 箱子供应商，使得 总浪费空间最小 。如果 无法 将所有包裹放入箱子中，请你返回 -1 。由于答案可能会
很大 ，请返回它对 ****109 + 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
**解释：** 选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。
总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。

提示：

  • n == packages.length
  • m == boxes.length
  • 1 <= n <= 105
  • 1 <= m <= 105
  • 1 <= packages[i] <= 105
  • 1 <= boxes[j].length <= 105
  • 1 <= boxes[j][k] <= 105
  • sum(boxes[j].length) <= 105
  • boxes[j] 中的元素 互不相同 。

方法一：排序 + 二分查找

思路与算法

我们首先将包裹按照尺寸从小到大进行排序。

随后我们枚举每一个供应商。对于第 i 个供应商提供的箱子，我们同样将这些箱子按照尺寸从小到大排序。

对于每一个包裹，如果它的尺寸为 x，那么我们选择的尺寸为 y 的箱子，需要满足 y \geq x。由于我们的目标是使得总浪费空间最小，因此每一个箱子浪费的空间都要尽可能小，即我们选择的 y 是满足 y \geq x 中最小的那个。

这样一来，我们就可以使用「逆向思维」来解决问题了。与其遍历每一个「包裹」选择「箱子」，我们不如遍历每一个「箱子」并匹配「包裹」。我们可以设计出如下的算法：

  • 我们依次遍历每一个箱子；

  • 如果当前遍历到的箱子的尺寸为 y，那么剩余所有的尺寸满足 x \leq y 的包裹，放入当前的箱子都是最优的。我们计算出这些包裹浪费的空间并进行累加，随后将这些包裹全部移除；

  • 当我们遍历完所有的箱子之后，就得到了总浪费空间，并且它是在我们选择第 i 个供应商的前提下最小的总浪费空间。

因为我们已经将包裹和箱子按照尺寸排好序了，所以上面的算法可以通过双指针来实现：即一个指针指向当前遍历到的箱子，一个指针指向尺寸最小的那个未被移除的包裹。然而这样做的时间复杂度为 O(nm + l)，其中 n，m，l 分别是包裹的数量，供应商的数量以及所有供应商提供的箱子的数量之和，会超出时间限制，因此我们需要对上面的算法进行优化。

优化

优化的方向较为直观：既然我们枚举的是供应商，以及每一个供应商提供的所有箱子，那么时间复杂度中的 m 和 l 是不可避免的，我们可以尝试优化掉包含 n 的项。

可以发现，包含 n 的项在上面的算法中对应的步骤是「枚举所有尺寸满足 x \leq y 的包裹」。由于包裹已经有序，我们可以将这一步枚举改为二分查找，即：

  • 假设当前遍历到的箱子的尺寸为 y，并且剩余的尺寸最小的包裹对应的下标为 pt；

  • 我们使用二分查找，找出「最大的尺寸满足 x \leq y 的包裹」，设其对应的下标为 pt}’，那么下标在 [\textit{pt}, \textit{pt}’] 范围内的所有包裹，放入尺寸为 y 的箱子都是最优的。这些包裹对应的浪费空间之和为：

\sum_{j=\textit{pt} }^{\textit{pt}’} (y - \textit{packages}[j])

即为：

(\textit{pt}’ - \textit{pt} + 1) y - \sum_{j=\textit{pt} }^{\textit{pt}’} \textit{packages}[j]

如果我们预处理出了包裹尺寸的前缀和，那么上式就可以在 O(1) 的时间内计算出。这样一来，我们一共需要进行 O(l) 次二分查找，每次二分查找的时间复杂度为 O(\log n)，总时间复杂度为 O(l \log n)。

代码

[sol1-C++]
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
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
private:
    using LL = long long;

    static constexpr int MOD = 1000000007;

public:
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        int n = packages.size();
        sort(packages.begin(), packages.end());

        // 计算数组 packages 的前缀和
        vector<LL> pre(n + 1);
        for (int i = 1; i <= n; ++i) {
            pre[i] = pre[i - 1] + packages[i - 1];
        }

        // 辅助函数，通过前缀和数组，得到数组 packages[left..right] 的和
        auto get = [&](int left, int right) {
            return pre[right + 1] - pre[left];
        };

        LL ans = LLONG_MAX;
        for (auto& box: boxes) {
            sort(box.begin(), box.end());
            // 小优化，如果最大包裹的尺寸大于最大箱子的尺寸，那么一定不满足，直接跳过
            if (packages.back() > box.back()) {
                continue;
            }

            // 初始化指针 pt，它指向还未被放入箱子的第一个包裹
            auto pt = packages.begin();
            // 总浪费空间
            LL total = 0;

            for (int y: box) {
                // 小优化，如果当前箱子 y 的尺寸小于 pt 指向的包裹，那么无需进行二分查找
                if (y < *pt) {
                    continue;
                }
                
                // pt'
                auto pt_next = prev(upper_bound(pt, packages.end(), y));
                
                total += (LL)(pt_next - pt + 1) * y - get(pt - packages.begin(), pt_next - packages.begin());
                pt = next(pt_next);
                // 小优化，如果所有包裹都已经被放入箱子，可以提前退出
                if (pt == packages.end()) {
                    break;
                }
            }
            ans = min(ans, total);
        }

        return (ans == LLONG_MAX ? -1 : ans % MOD);
    }
};
[sol1-Python3]
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
class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        packages.sort()
        # 计算数组 packages 的前缀和
        pre = list(accumulate(packages, initial=0))

        # 辅助函数，通过前缀和数组，得到数组 packages[left..right] 的和
        get = lambda left, right: pre[right + 1] - pre[left]
        
        ans = float("inf")
        for box in boxes:
            box.sort()
            # 小优化，如果最大包裹的尺寸大于最大箱子的尺寸，那么一定不满足，直接跳过
            if packages[-1] > box[-1]:
                continue

            # 初始化指针 pt，它指向还未被放入箱子的第一个包裹
            pt = 0
            # 总浪费空间
            total = 0

            for y in box:
                # 小优化，如果当前箱子 y 的尺寸小于 pt 指向的包裹，那么无需进行二分查找
                if y < packages[pt]:
                    continue
                
                # pt'
                pt_next = bisect_right(packages, y, pt) - 1
                
                total += (pt_next - pt + 1) * y - get(pt, pt_next)
                pt = pt_next + 1
                # 小优化，如果所有包裹都已经被放入箱子，可以提前退出
                if pt == len(packages):
                    break
            
            ans = min(ans, total)

        return -1 if ans == float("inf") else ans % MOD

复杂度分析

  • 时间复杂度：O(n \log n + l \log l + l \log n)，其中 n 和 l 分别是包裹的数量，以及所有供应商提供的箱子的数量之和。由于供应商的数量 m 是一定小于等于 l 的，因此时间复杂度中没有出现 m 也是很正常的。

    • 对数组 packages 排序的时间复杂度为 O(n \log n)；

    • 计算前缀和的时间复杂度为 O(n)，在渐进意义下可以忽略；

    • 对数组 boxes 中的每一个数组排序的总时间复杂度为 O(l \log l)；

    • 一共需要进行 O(l) 次二分查找，每次的时间复杂度为 O(\log n)，总时间复杂度为 O(l \log n)。

  • 空间复杂度：O(n + \log l)。我们需要 O(n) 的空间存储前缀和，O(\log n) 和 O(\log l) 的空间作为排序使用的栈空间，其中 O(\log n) 项在渐近意义下可以忽略。

 Comments
On this page
1889-装包裹的最小浪费空间