Problem

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith 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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5
6
7
8
9

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.

Solution

Method 1 – Greedy + Sorting

Intuition

To maximize the number of full bags, always fill the bags that need the fewest rocks first. This way, we use the additional rocks efficiently and fill as many bags as possible.

Approach

  1. For each bag, calculate how many rocks are needed to fill it: need[i] = capacity[i] - rocks[i].
  2. Sort the need array in ascending order.
  3. Iterate through the sorted need array:
  • For each bag, if need[i] is less than or equal to the remaining additionalRocks, fill the bag and decrease additionalRocks accordingly.
  • If not enough rocks remain, stop.
  1. Count and return the number of bags filled.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
   int maximumBags(vector<int>& cap, vector<int>& rocks, int add) {
      vector<int> need;
      for (int i = 0; i < cap.size(); ++i)
        need.push_back(cap[i] - rocks[i]);
      sort(need.begin(), need.end());
      int ans = 0;
      for (int n : need) {
        if (n <= add) {
           ++ans;
           add -= n;
        } else break;
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func maximumBags(capacity []int, rocks []int, add int) int {
   n := len(capacity)
   need := make([]int, n)
   for i := 0; i < n; i++ {
      need[i] = capacity[i] - rocks[i]
   }
   sort.Ints(need)
   ans := 0
   for _, v := range need {
      if v <= add {
        ans++
        add -= v
      } else {
        break
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
   public int maximumBags(int[] cap, int[] rocks, int add) {
      int n = cap.length;
      int[] need = new int[n];
      for (int i = 0; i < n; i++)
        need[i] = cap[i] - rocks[i];
      Arrays.sort(need);
      int ans = 0;
      for (int v : need) {
        if (v <= add) {
           ans++;
           add -= v;
        } else break;
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
   fun maximumBags(cap: IntArray, rocks: IntArray, add: Int): Int {
      val need = cap.indices.map { cap[it] - rocks[it] }.sorted()
      var ans = 0
      var rem = add
      for (v in need) {
        if (v <= rem) {
           ans++
           rem -= v
        } else break
      }
      return ans
   }
}
 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:
      need = [c - r for c, r in zip(capacity, rocks)]
      need.sort()
      ans = 0
      for n in need:
        if n <= additionalRocks:
           ans += 1
           additionalRocks -= n
        else:
           break
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
   pub fn maximum_bags(cap: Vec<i32>, rocks: Vec<i32>, mut add: i32) -> i32 {
      let mut need: Vec<i32> = cap.iter().zip(rocks.iter()).map(|(c, r)| c - r).collect();
      need.sort();
      let mut ans = 0;
      for n in need {
        if n <= add {
           ans += 1;
           add -= n;
        } else {
           break;
        }
      }
      ans
   }
}

Complexity

  • Time: O(n log n) (for sorting)
  • Space: O(n) (for the need array)