Задача: Максимальное количество сумок, полностью заполненных камнями

Условие: дается n-сумок, пронумерованных с нуля. Дается также два массива, проиндексированных аналогичным образом: capacity и rocks. i-а сумка может вмещать capacity[i] камней и в текущий момент содержит уже rocks[i] каменей. Помимо этого дается еще additionalRocks, число камней, которые можно добавить в произвольную сумку.

Необходимо вычислить максимальное количество сумок, которое получится при ситуации, когда все дополнительные камни размещены.

Пример:

Ввод: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2

Вывод: 3

Ввод: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100

Вывод: 3

Решение:

Сложность:

Временная O(nlogn)

Пространственная O(n)

Python code:

    def maximumBags(self, capacity, rocks, x):
        count = sorted(c - r for c,r in zip(capacity, rocks))[::-1]
        while count and x and count[-1] <= x:
            x -= count.pop()
        return len(rocks) - len(count)