Задача. Оптимальное заполнение мешков

Даны n мешков и два целочисленных массива capacity и rocks.

• i-й мешок может вмещать максимум камней вместимостью capacity[i] и содержит rocks[i] камней.
• Также дано целое число additionalRocks - количество дополнительных камней, которые можно поместить в любой из мешков.

Необходимо вернить МАКСИМАЛЬНОЕ количество мешков, которые могут иметь полную вместимость после размещения дополнительных камней в некоторых мешках.

Пример

• capacity = [2,3,4,5]
• rocks = [1,2,4,4]
• additionalRocks = 2

Output: 3

Пояснение: по одному камню кладем в 1й и 2й мешок. Тогда количество камней в каждом мешке равно [2,3,4,4]. И первые 3 мешка полностью заполнены.

Разбор

Классический жадный алгоритм.

1. На 1м этапе найдем размер свободного места в мешках.
2. На 2м этапе отсортируем массив по возрастанию свободных мест в мешках.
3. На 3м этапе будем использовать дополнительные камни для заполнения мешков пока это возможно.
4. Вернем количество полностью заполненных мешков.

Реализация

static int MaxBags(int[] capacity, int[] rocks, int additionalRocks) {
	for (int i = 0; i < capacity.Length; i++)
	{
		capacity[i] -= rocks[i];
	}

	Array.Sort(capacity);

	int result = 0;
	for (int i = 0; i < capacity.Length; i++)
	{
		if (capacity[i] > 0 && additionalRocks == 0)
			return result;

		if (capacity[i] == 0)
		{
			result++;    
		}
		else if (capacity[i] <= additionalRocks)
		{
			additionalRocks -= capacity[i];
			result++;
		}
	}

	return result;
}

https://gist.github.com/unilecs/8ab18a06ecff6e47d48402499c90ec75

Python:
https://gist.github.com/unilecs/ebf505863c07ff797cf3c59a0b9aa014

Play-test (C#):
https://dotnetfiddle.net/kaLbf9