LeetCode 题解工作台
重新分装苹果
给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。 一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。 请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
为了使得需要的箱子数量尽可能少，我们应该优先使用容量大的箱子。因此，我们可以对箱子按照容量从大到小排序，然后依次使用箱子，直到所有的苹果都被分装完，返回此时使用的箱子数量。 时间复杂度 $O(m \times \log m + n)$，空间复杂度 $O(\log m)$。其中 和 分别是数组 和 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。
一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。
请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。
注意，同一个包裹中的苹果可以分装到不同的箱子中。
示例 1：
输入：apple = [1,3,2], capacity = [4,3,1,5,2] 输出：2 解释：使用容量为 4 和 5 的箱子。 总容量大于或等于苹果的总数，所以可以完成重新分装。
示例 2：
输入：apple = [5,5,5], capacity = [2,4,2,7] 输出：4 解释：需要使用所有箱子。
提示：
1 <= n == apple.length <= 501 <= m == capacity.length <= 501 <= apple[i], capacity[i] <= 50- 输入数据保证可以将包裹中的苹果重新分装到箱子中。
解题思路
方法一：贪心 + 排序
为了使得需要的箱子数量尽可能少，我们应该优先使用容量大的箱子。因此，我们可以对箱子按照容量从大到小排序，然后依次使用箱子，直到所有的苹果都被分装完，返回此时使用的箱子数量。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度。
class Solution:
def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
capacity.sort(reverse=True)
s = sum(apple)
for i, c in enumerate(capacity, 1):
s -= c
if s <= 0:
return i
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m log m + n) due to sorting the capacity array and iterating over n packs. Space complexity is O(1) extra space if in-place sorting is used, otherwise O(m) for sorted copy. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if candidate sorts the capacity array before allocation.
- question_mark
Looks for correct greedy allocation respecting remaining sum invariant.
- question_mark
Wants explanation for why the fewest boxes are sufficient, not just any allocation.
常见陷阱
外企场景- error
Failing to sort capacities leads to using more boxes than necessary.
- error
Not maintaining the sum invariant can cause incorrect allocation and overshoot.
- error
Confusing pack count with box capacity can produce wrong minimum count.
进阶变体
外企场景- arrow_right_alt
Allow boxes to hold multiple packs but with a maximum total capacity constraint.
- arrow_right_alt
Change problem to find maximum number of apple packs in exactly k boxes.
- arrow_right_alt
Introduce weight limits per apple pack in addition to box capacity.