
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:
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]
).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.
Sort the bags based on their deficits.
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 fromadditionalRocks
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.
- If the current bag's deficit can be met with the remaining
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
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.
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:
- Start by determining the number of bags and initialize a counter to track how many can be completely filled.
- 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.
- 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.
- 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.
- 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.
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 theextraStones
to fill each bag:- Subtract the required stones from
extraStones
and increment thecount_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.
- Subtract the required stones from
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
.
No comments yet.