What is the key pattern in solving the Maximum Bags With Full Capacity of Rocks problem?

The key pattern is using a greedy approach combined with sorting to prioritize filling the bags with the smallest remaining capacity first.

How do I handle large inputs efficiently for this problem?

To handle large inputs efficiently, you should focus on the sorting step (O(n log n)) and ensure that you're using a greedy approach to minimize unnecessary computations.

What edge cases should I be aware of when solving this problem?

You should account for edge cases where no additional rocks are needed or where all bags are already full. Also, consider the scenario where the number of additional rocks exceeds the total capacity required to fill the bags.

Is the Maximum Bags With Full Capacity of Rocks problem solvable in linear time?

No, the problem involves sorting the bags by their remaining capacity, which requires O(n log n) time. After sorting, the greedy approach runs in linear time (O(n)).

Can the greedy approach fail in this problem?

The greedy approach can fail if you don't sort the bags by remaining capacity, as this can result in a less optimal solution. Sorting ensures that you always fill the bags that need the fewest rocks first.

#2279

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

装满石头的背包的最大数量

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，…

数组贪心排序

题目描述

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往任意背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的最大数量。

示例 1：

输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。

示例 2：

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3
解释：
8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。

提示：

n == capacity.length == rocks.length
1 <= n <= 5 * 10⁴
1 <= capacity[i] <= 10⁹
0 <= rocks[i] <= capacity[i]
1 <= additionalRocks <= 10⁹

lightbulb

解题思路

方法一：排序 + 贪心

我们首先将每个背包的剩余容量计算出来，然后对剩余容量进行排序，接着我们从小到大遍历剩余容量，将额外的石头放入背包中，直到额外的石头用完或者背包的剩余容量用完为止，返回此时的背包数量即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为背包的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumBags(
        self, capacity: List[int], rocks: List[int], additionalRocks: int
    ) -> int:
        for i, x in enumerate(rocks):
            capacity[i] -= x
        capacity.sort()
        for i, x in enumerate(capacity):
            additionalRocks -= x
            if additionalRocks < 0:
                return i
        return len(capacity)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently handle large inputs (up to 50,000 bags)?
question_mark
Is the candidate familiar with sorting algorithms and their time complexity?
question_mark
Does the candidate understand the trade-off between greedy algorithms and optimal solutions?

warning

常见陷阱

外企场景

error
Not sorting the bags by remaining capacity, which could result in suboptimal placement of rocks.
error
Overlooking edge cases where additional rocks are not needed or cannot be used effectively.
error
Failing to account for the possibility that some bags might already be full before distributing the extra rocks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there are multiple ways to distribute the additional rocks but only one optimal solution exists?
arrow_right_alt
How would you approach the problem if the additional rocks can be distributed only among certain bags (restricted bags)?
arrow_right_alt
What if the bags had different weight limits, and only a limited number of bags could be chosen for rock distribution?

help

常见问题

外企场景

继续练习

#2271 毯子覆盖的最多白色砖块数 #2294 划分数组使最大差为 K #2234 花园的最大总美丽值