Maximum Bags With Full Capacity of Rocks

Problem Description

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The i-th bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags. Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.

Key Insights

• Calculate the remaining capacity for each bag by subtracting the current number of rocks from the maximum capacity.
• Sort the bags based on their remaining capacity in ascending order.
• Use the additional rocks to fill the bags with the smallest remaining capacity first, maximizing the number of bags that can be filled.
• Stop when you run out of additional rocks or when all bags are full.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the bags. Space Complexity: O(1) - only a constant amount of extra space is used.

Solution

The solution involves the following steps:

1. Calculate the remaining capacity for each bag.
2. Sort the remaining capacities in ascending order.
3. Iterate through the sorted list, using the additional rocks to fill each bag until either all rocks are used or all bags are full. This greedy approach ensures that we maximize the number of bags filled to capacity.

Code Solutions