Maximum Bags With Full Capacity of Rocks — LeetCode 2279 Python Solution

The problem

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks.

Example

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.

Python solution

class Solution:
    def maximumBags(
        self, capacity: List[int], rocks: List[int], additionalRocks: int
    ) -> int:
        for i, x in enumerate(rocks):
            capacity[i] -= x
        capacity.sort()
        for i, x in enumerate(capacity):
            additionalRocks -= x
            if additionalRocks < 0:
                return i
        return len(capacity)

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2279. Maximum Bags With Full Capacity of Rocks is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems