Question

2279. Maximum Bags With Full Capacity of Rocks

中文文档

Description

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._

 

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

Solutions

Solution 1

class Solution:
  def maximumBags(
    self, capacity: List[int], rocks: List[int], additionalRocks: int
  ) -> int:
    d = [a - b for a, b in zip(capacity, rocks)]
    d.sort()
    ans = 0
    for v in d:
      if v <= additionalRocks:
        ans += 1
        additionalRocks -= v
    return ans

class Solution {
  public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
    int n = capacity.length;
    int[] d = new int[n];
    for (int i = 0; i < n; ++i) {
      d[i] = capacity[i] - rocks[i];
    }
    Arrays.sort(d);
    int ans = 0;
    for (int v : d) {
      if (v <= additionalRocks) {
        ++ans;
        additionalRocks -= v;
      } else {
        break;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
    int n = capacity.size();
    vector<int> d(n);
    for (int i = 0; i < n; ++i) d[i] = capacity[i] - rocks[i];
    sort(d.begin(), d.end());
    int ans = 0;
    for (int& v : d) {
      if (v > additionalRocks) break;
      ++ans;
      additionalRocks -= v;
    }
    return ans;
  }
};

func maximumBags(capacity []int, rocks []int, additionalRocks int) int {
  n := len(capacity)
  d := make([]int, n)
  for i, v := range capacity {
    d[i] = v - rocks[i]
  }
  sort.Ints(d)
  ans := 0
  for _, v := range d {
    if v > additionalRocks {
      break
    }
    ans++
    additionalRocks -= v
  }
  return ans
}

function maximumBags(capacity: number[], rocks: number[], additionalRocks: number): number {
  const n = capacity.length;
  const diffs = capacity.map((c, i) => c - rocks[i]);
  diffs.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0; i < n && (diffs[i] === 0 || diffs[i] <= additionalRocks); i++) {
    ans++;
    additionalRocks -= diffs[i];
  }
  return ans;
}

impl Solution {
  pub fn maximum_bags(capacity: Vec<i32>, rocks: Vec<i32>, mut additional_rocks: i32) -> i32 {
    let n = capacity.len();
    let mut diffs = vec![0; n];
    for i in 0..n {
      diffs[i] = capacity[i] - rocks[i];
    }
    diffs.sort();
    for i in 0..n {
      if diffs[i] > additional_rocks {
        return i as i32;
      }
      additional_rocks -= diffs[i];
    }
    n as i32
  }
}