Show problems as
Classic problem #2279MediumArrayGreedySorting

Maximum Bags With Full Capacity of Rocks

Real-world version: Crates Filled to the Brim
Tracked in this browser only
Read Maximum Bags With Full Capacity of Rocks on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A yard holds n crates. Crate i takes capacity[i] bricks in total and already holds rocks[i] of them. A delivery brings additionalRocks more bricks, and each may be dropped into any crate that is not yet full.

Return the largest number of crates that can be filled to the brim.

Examples

Example 1

Input
capacity = [3, 6, 7], rocks = [1, 6, 2], additionalRocks = 5
Output
2

The second crate is already full. Dropping 2 bricks into the first fills it, and the 3 bricks left do not cover the 5 the third crate still needs.

Example 2

Input
capacity = [4, 3, 2, 1], rocks = [0, 0, 0, 0], additionalRocks = 6
Output
3

Filling the crates needing 1, 2 and 3 bricks uses all six bricks and fills three crates.

Example 3

Input
capacity = [5, 5, 5], rocks = [5, 5, 5], additionalRocks = 1
Output
3

Every crate is already filled to the brim, so all three count and the delivery is not needed.

Constraints

  • 1 <= capacity.length <= 50000
  • capacity.length == rocks.length
  • 1 <= capacity[i] <= 10^9
  • 0 <= rocks[i] <= 10^9
  • rocks[i] <= capacity[i] for every crate
  • 1 <= additionalRocks <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def crates_filled(capacity: list[int], rocks: list[int], additionalRocks: int) -> int:
Java
public int cratesFilled(int[] capacity, int[] rocks, int additionalRocks)

More on the same topics