Maximum bags with full capacity of rocks

Array Greedy Sorting

68.0% acceptance

Feb 25, 2026

1768

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_bags(capacity: Vec<i32>, rocks: Vec<i32>, additional_rocks: i32) -> i32 {
    let mut gaps: Vec<i32> = capacity.iter().zip(rocks.iter())
      .map(|(&c, &r)| c - r)
      .collect();
    gaps.sort_unstable();
    let mut remaining = additional_rocks as i64;
    let mut count = 0;
    for gap in gaps {
      if remaining >= gap as i64 {
        remaining -= gap as i64;
        count += 1;
      } else {
        break;
      }
    }
    count
  }
}