Maximum Bags With Full Capacity of Rocks

Updated on 16 June, 2025
Maximum Bags With Full Capacity of Rocks header image

Problem Statement

Given n bags, each with a specific capacity to hold rocks, described by the capacity array, and an initial number of rocks each bag contains described by the rocks array, you need to determine the maximum number of bags that can be filled to their capacity. Alongside this, you have an additionalRocks count of rocks that you can distribute among these bags as you see fit. The problem requires calculating the maximum number of bags that could be filled to their total capacity using the rocks they initially contain combined with the distribution of the additional rocks.

Examples

Example 1

Input:

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

Output:

3

Explanation:

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

Explanation:

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

Approach and Intuition

To solve this problem, we need to determine the strategy that allows the maximum number of bags to reach their full capacity. It can be approached using the following steps:

  1. Calculate the deficit for each bag, which is the number of rocks needed to fill each bag to its capacity (i.e., capacity[i] - rocks[i]).

  2. Aim to fill the bags with the smallest deficit first, as this allows us to use the available rocks to maximize the number of fully filled bags.

  3. Sort the bags based on their deficits.

  4. Traverse through the sorted list and try to fill each bag:

    • If the current bag's deficit can be met with the remaining additionalRocks, deduct the required rocks from additionalRocks and increase your count of fully filled bags.
    • If the deficit of the current bag cannot be met (i.e., additionalRocks becomes less than the required rocks to fill that bag), break out of the loop as no further bags can be filled completely.

By the end of this procedure, the count of fully filled bags will represent the maximum number of bags that can be filled using the initial and additional rocks. This methodology ensures that we utilize the available rocks in the most efficient way to maximize the number of fully filled bags.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int maxFilledBags(vector<int>& capacities, vector<int>& stones, int extraStones) {
        int bagsCount = int(capacities.size()), completelyFilled = 0;
    
        // Calculate remaining capacity for each bag.
        vector<int> neededCapacity(bagsCount);
    
        for (int i = 0; i < bagsCount; ++i)
            neededCapacity[i] = capacities[i] - stones[i];
        sort(neededCapacity.begin(), neededCapacity.end());
    
        // Attempt to fill bags in order of their needed capacity.
        for (int i = 0; i < bagsCount; ++i) {
            // Check if enough stones are available to fill the current bag.
            if (extraStones >= neededCapacity[i]) {
                extraStones -= neededCapacity[i];
                completelyFilled++;
            }
            else {
                break;
            }
        }
            
        // Final count of completely filled bags.
        return completelyFilled;
    }
};

The solution involves implementing a function maxFilledBags in C++ that determines the maximum number of bags that can be completely filled given arrays of their capacities and current stone counts, and an additional number of extra stones available.

  • Start by calculating the difference between the bag capacities and the current number of stones in each bag. This yields the number of additional stones required for each bag.
  • Sort these requirements in ascending order so that bags requiring fewer stones to be filled are considered first.
  • Sequentially allocate the extra stones to the bags with the smallest requirement, thus maximizing the number of fully filled bags.
  • Return the total count of bags that can be completely filled with the given total stones.

This process enhances efficiency by filling those bags first that are closest to their capacity, ensuring optimal utilization of the extra stones provided.

java
class Solution {
    public int fillMaxBags(int[] capacities, int[] filled, int extraRocks) {
        int count = capacities.length, completelyFilled = 0;
            
        int[] spaceLeft = new int[count];
        for (int i = 0; i < count; ++i)
            spaceLeft[i] = capacities[i] - filled[i];
        Arrays.sort(spaceLeft);
        
        for (int i = 0; i < count; ++i) {
            if (extraRocks >= spaceLeft[i]) {
                extraRocks -= spaceLeft[i];
                completelyFilled++;
            }
            else
                break;
        }
            
        return completelyFilled;
    }
}

The presented Java solution efficiently calculates the maximum number of bags that can be filled to their capacity given initial bag capacities, rocks already in them, and additional available rocks. Here's a concise overview of how the solution operates:

  1. Start by determining the number of bags and initialize a counter to track how many can be completely filled.
  2. Calculate the remaining space in each bag by subtracting the rocks already present from the total capacity of each bag. Store these values in an array.
  3. Sort the array of space left in the bags to prioritize filling the ones with the least space left first, which optimizes the number of bags that can be completely filled using the given extra rocks.
  4. Iterate through the sorted list, and as long as you have sufficient extra rocks remaining, subtract the needed rocks from the extra rocks and increase your count of completely filled bags.
  5. Return the count of completely filled bags once either all bags are filled or you run out of extra rocks.

This approach ensures that you maximize the number of fully filled bags by focusing on filling the smaller gaps first, making efficient use of the available extra rocks.

python
class Solution:
    def maxFilledBags(self, capacities: List[int], stones: List[int], extraStones: int) -> int:
        leftover_space = [cap - stone for cap, stone in zip(capacities, stones)]
        leftover_space.sort()
        count_full = 0
            
        for space in leftover_space:
            if extraStones >= space:
                extraStones -= space
                count_full += 1
            else:
                break
            
        return count_full

The code defines a Python function maxFilledBags which determines the maximum number of bags that can be filled to their respective capacity with rocks. It takes three parameters: capacities, a list of integers representing the maximum capacity of each bag; stones, a list of integers indicating the initial number of stones in each bag; and extraStones, an integer representing additional stones available to fill the bags.

Here's a brief rundown of how this solution works:

  • Calculate leftover_space for each bag by subtracting the stones already in the bag from the total capacity of the bag.
  • Sort leftover_space in ascending order to prioritize bags that require fewer stones to be filled.
  • Initialize a counter count_full to keep track of how many bags are filled to capacity.
  • Iterate through each space requirement in leftover_space, using up the extraStones to fill each bag:
    • Subtract the required stones from extraStones and increment the count_full if the bag can be filled with the available stones.
    • Stop the process if there are not enough extraStones to fill the next bag.

The function finally returns count_full, the count of bags that could be filled to capacity. This method optimally uses the available stones by filling the smallest unfilled bags first, ensuring maximal usage of extraStones.

Comments

No comments yet.