What is the optimal way to minimize wasted space in the Minimum Space Wasted From Packaging problem?

The optimal approach involves using binary search to find the smallest possible box size that fits the packages, combined with sorting and prefix sums for efficient calculations.

How does binary search help in the Minimum Space Wasted From Packaging problem?

Binary search allows you to efficiently explore the valid space of box sizes, narrowing down the best fitting box for each package while minimizing the total wasted space.

Can there be cases where no box fits the package in the Minimum Space Wasted From Packaging problem?

Yes, if no box is large enough to fit a package, the answer should be -1, indicating that the package cannot be packed.

What is the time complexity of the solution for the Minimum Space Wasted From Packaging problem?

The time complexity is O(n log m), where n is the number of packages and m is the number of suppliers, primarily due to the sorting and binary search steps.

Are there any edge cases to consider in the Minimum Space Wasted From Packaging problem?

Yes, edge cases include scenarios where no box fits a package or when multiple suppliers have similar box sizes. It's important to handle these cases correctly to avoid incorrect results.

#1889

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

装包裹的最小浪费空间

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

数组二分查找排序前缀和

题目描述

给你 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 。由于答案可能会很大，请返回它对 10⁹ + 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 <= 10⁵
1 <= m <= 10⁵
1 <= packages[i] <= 10⁵
1 <= boxes[j].length <= 10⁵
1 <= boxes[j][k] <= 10⁵
sum(boxes[j].length) <= 10⁵
boxes[j] 中的元素 互不相同 。

lightbulb

解题思路

方法一：排序 + 二分查找

我们首先对包裹的尺寸数组 $packages$ 进行排序。

然后遍历每个供应商的箱子数组 $boxes$ ，对于每个箱子数组 $boxes$ ，我们也对其进行排序。

如果当前箱子数组中最大的箱子尺寸小于包裹数组中最大的包裹尺寸，那么我们就可以跳过这个供应商，因为这个供应商的箱子无法装下最大的包裹。否则，我们从小到大遍历当前供应商的每个箱子 $b$ ，用一个指针 $i$ 指向当前待装箱的包裹。

接下来，我们在数组 $packages$ 中二分查找，找到第一个尺寸大于 $b$ 的包裹 $packages[j]$ 。那么我们可以用箱子 $b$ 装下 $packages[i..j-1]$ 中的所有包裹，此时总空间为 $b \times (j - i)$ 。然后我们将指针 $i$ 移动到 $j$ ，继续寻找下一个箱子的装包情况。

遍历完该供应商的所有箱子后，我们就可以得到该供应商所需的箱子总空间。我们遍历所有供应商，找到所需箱子的最小总空间，那么浪费的空间就是总空间减去所有包裹的总尺寸。

时间复杂度 $O(n \times \log n + l \times \log l + l \times \log n)$ ，空间复杂度 $O(\log n + \log l)$ 。其中 $n$ 是包裹的数量，而 $l$ 是所有箱子的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        mod = 10**9 + 7
        ans = inf
        packages.sort()
        for box in boxes:
            box.sort()
            if packages[-1] > box[-1]:
                continue
            s = i = 0
            for b in box:
                j = bisect_right(packages, b, lo=i)
                s += (j - i) * b
                i = j
            ans = min(ans, s)
        if ans == inf:
            return -1
        return (ans - sum(packages)) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to optimize search within the box sizes using binary search.
question_mark
Proficiency in sorting algorithms and their applications to packing problems.
question_mark
Understanding the use of prefix sums in cumulative calculations.

warning

常见陷阱

外企场景

error
Failing to handle cases where no box fits a package, leading to incorrect results.
error
Not optimizing the solution with binary search, resulting in inefficient brute-force solutions.
error
Overcomplicating the solution with unnecessary data structures when a simple sorting and binary search approach is sufficient.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing multiple suppliers to provide the same box sizes and exploring different packaging strategies.
arrow_right_alt
Extending the problem to support 3D box sizes and packages.
arrow_right_alt
Adding constraints that limit the number of boxes that can be used per supplier.

help

常见问题

外企场景

继续练习

#1838 最高频元素的频数 #2234 花园的最大总美丽值 #2251 花期内花的数目