Maximum Bags With Full Capacity of Rocks

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

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;
    }
};