#2279

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Bags With Full Capacity of Rocks

Maximize the number of bags filled to capacity by distributing additional rocks using a greedy approach.

Problem Statement

You have n bags, each having a certain capacity and current number of rocks. You are given an array of capacities and an array of the current number of rocks in each bag. Additionally, you're given a number of extra rocks you can place into any of the bags. Your task is to determine the maximum number of bags that can be filled to their full capacity after distributing the extra rocks optimally.

To solve this, consider the difference between the capacity and the current number of rocks for each bag. The goal is to place as many additional rocks as possible into bags with the smallest remaining capacity first, maximizing the number of bags that can be filled to capacity.

Examples

Example 1

Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2

Output: 3

Place 1 rock in bag 0 and 1 rock in bag 1. The number of rocks in each bag are now [2,3,4,4]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that there may be other ways of placing the rocks that result in an answer of 3.

Example 2

Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100

Output: 3

Place 8 rocks in bag 0 and 2 rocks in bag 2. The number of rocks in each bag are now [10,2,2]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that we did not use all of the additional rocks.

Constraints

n == capacity.length == rocks.length
1 <= n <= 5 * 104
1 <= capacity[i] <= 109
0 <= rocks[i] <= capacity[i]
1 <= additionalRocks <= 109

Solution Approach

Greedy Approach

Sort the bags based on their remaining capacity (capacity[i] - rocks[i]). Then, start filling the bags from the smallest remaining capacity to the largest. For each bag, check if you can completely fill it using the available additional rocks. Deduct the number of rocks used and move to the next smallest bag. Stop once there are no more rocks to distribute or no more bags can be filled.

Sorting and Efficient Allocation

Sorting the bags by the difference between the capacity and the current rock count ensures that you can prioritize bags that require fewer rocks to reach full capacity. This minimizes wasted resources and helps in achieving the goal of filling the maximum number of bags. After sorting, a simple greedy iteration over the sorted bags will complete the task.

Edge Case Handling

Edge cases include scenarios where there are no additional rocks or all bags are already at full capacity. In such cases, no additional rocks are needed, and the solution should return the count of already full bags. Another edge case is when there are more additional rocks than required, where only the number of bags that can be fully filled matters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is dominated by the sorting step, which is O(n log n), where n is the number of bags. After sorting, the greedy approach runs in O(n) time, making the total time complexity O(n log n). The space complexity is O(n) due to the storage required for sorting the bags and calculating the remaining capacities.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Sorting + Greedy

First, we calculate the remaining capacity of each bag, then sort the remaining capacities. Next, we traverse the remaining capacities from smallest to largest, putting the extra stones into the bags until the extra stones are used up or the remaining capacities of the bags are exhausted. Finally, we return the number of bags at this point.

1

2

3

4

5

6

7

8

9

10

11

12

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)

Continue Practicing

#2271 maximum white tiles covered by a carpet #2294 partition array such that maximum difference is k #2234 maximum total beauty of the gardens