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

Условие: дается 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

Решение:

Python3 Go

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        diff = [capacity[i] - rocks[i] for i in range(len(rocks))]
        heapify(diff)
        bags = 0
        while diff and additionalRocks >= diff[0]:
            additionalRocks -= heappop(diff)
            bags += 1
        return bags

func maximumBags(capacity []int, rocks []int, additionalRocks int) int {
    for i := range rocks {
        capacity[i] -= rocks[i]
    }
    sort.Ints(capacity)
    i := 0
    for i < len(capacity) && additionalRocks >= capacity[i] {
        additionalRocks -= capacity[i]
        i += 1
    }
    return i
}