装包裹的最小浪费空间

标签: 数组 二分查找 前缀和 排序

难度: Hard

给你 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] 中的元素 互不相同 。

Submission

运行时间: 183 ms

内存: 35.2 MB

from typing import List

'''
分析：
f(j)（i,j]货物总数量
g(j)表示(i,j]区间内的货物总尺寸
h(j) = j * f(j)-g(j)
S = sun(h(j))
'''


class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        biggest = max(packages) + 1
        # 不同大小箱子数
        f = [0] * biggest

        g = [0] * biggest
        res = float('inf')
        for i in packages: f[i] += 1
        # 更新g
        for i in range(biggest): g[i] = f[i] + g[i - 1]
        # 遍历供应商
        for box in boxes:
            last, tmp, box = 0, 0, sorted(box)
            # 装不下
            if box[-1] < biggest - 1:
                continue
            for j in box:
                # 遇到可以装下所有的
                if j >= biggest:
                    tmp += (g[-1] - g[last]) * j
                    break
                tmp += (g[j] - g[last]) * j
                last = j
            res = min(res, tmp)
        return (res - sum(packages)) % (10 ** 9 + 7) if res != float('inf') else -1

Explain

此题解利用前缀和和排序来最小化浪费空间。首先，对包裹数组进行排序，并计算包裹尺寸的频率（f数组）和前缀和（g数组）。然后，对于每个供应商提供的箱子，按箱子尺寸排序，使用二分查找方法寻找每个包裹可以放入的最小箱子。计算每个箱子的浪费空间并累加，最后选取浪费空间最小的供应商。如果某个供应商的最大箱子尺寸小于最大包裹尺寸，则此供应商不能装下所有包裹。该算法针对每个供应商计算浪费空间，最后返回最小值。

时间复杂度: O(m(b log b + b log n))

空间复杂度: O(biggest)

from typing import List


class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        packages.sort() # 对包裹进行排序
        biggest = max(packages) + 1
        f = [0] * biggest # 存储每个尺寸的包裹数量
        g = [0] * biggest # 存储前缀和
        res = float('inf')
        for i in packages: f[i] += 1
        for i in range(1, biggest): g[i] = g[i - 1] + f[i] # 计算前缀和
        # 遍历每个供应商的箱子
        for box in boxes:
            last, tmp, box = 0, 0, sorted(box) # 对箱子进行排序
            if box[-1] < packages[-1]:
                continue # 如果最大箱子小于最大包裹，则跳过
            for j in box:
                if j >= packages[-1]:
                    tmp += (g[packages[-1]] - g[last]) * j
                    break
                tmp += (g[j] - g[last]) * j
                last = j
            res = min(res, tmp)
        return (res - sum(packages)) % (10 ** 9 + 7) if res != float('inf') else -1 # 如果res未更新，返回-1，否则返回结果

Explore

在题解中，前缀和数组`g`是用于快速计算某个范围内包裹尺寸总和的工具。首先，我们创建一个频率数组`f`，其中`f[i]`表示尺寸为`i`的包裹的数量。然后，前缀和数组`g`的每个元素`g[i]`存储了所有小于等于`i`尺寸的包裹数量的累加和。具体计算方法是：对于`g`的每个元素，`g[i]`等于`g[i-1]`加上`f[i]`。这样，`g[i]`就能在O(1)时间内给出任何尺寸范围的包裹数量总和，这对于后续计算每个箱子可以装载的包裹数量极为关键和有效。

尽管题解中没有直接使用二分查找方法，但通常在类似的问题中，二分查找可以用来在已排序的箱子数组中快速找到能够容纳当前考虑的包裹尺寸的最小箱子。具体来说，对于每个包裹尺寸，我们可以使用二分查找在箱子数组中找到第一个大于等于该尺寸的箱子。这样可以确保包裹被放入尽可能小的箱子中，从而最小化浪费空间。在本题解中，通过对箱子进行排序并顺序遍历，实现了类似的效果，即为每个包裹尺寸段找到合适的箱子。

模运算`(10 ** 9 + 7)`在编程竞赛和许多编程问题中常用来防止整数溢出，同时也用于保持结果的规模可控，使其在一定的范围内。数字`10 ** 9 + 7`是一个大质数，常用作模数，因为它可以减小哈希冲突的可能性，并且在大多数编程语言中不会导致整数溢出。在这个题解中，考虑到可能需要处理大量的数据和大的数值计算，使用模运算可以有效避免结果超出标准整数范围的问题。