1889-装包裹的最小浪费空间(Minimum Space Wasted From Packaging)
发表于：2021-12-03 | 分类： 困难
字数统计: 1k | 阅读时长: 5分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/minimum-space-wasted-from-packaging

英文原文

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.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
  • The elements in boxes[j] are distinct.

中文题目

给你 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$，并且剩余的尺寸最小的包裹对应的下标为 $\textit{pt}$；

  • 我们使用二分查找，找出「最大的尺寸满足 $x \leq y$ 的包裹」，设其对应的下标为 $\textit{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++]
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]
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$ 也是很正常的。

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

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

    • 对数组 $\textit{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)$ 项在渐近意义下可以忽略。

统计信息

通过次数 提交次数 AC比率
2239 8275 27.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
排序 数组 二分查找 前缀和
上一篇:
1888-使二进制字符串字符交替的最少反转次数(Minimum Number of Flips to Make the Binary String Alternating)
下一篇:
1909-删除一个元素使数组严格递增(Remove One Element to Make the Array Strictly Increasing)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo