Ctrl K

Запас сил на все дела

Сложная
Есть список дел chores, где chores[i] = [cost, need]: дело отнимает cost единиц сил, но взяться за него можно, только если сейчас сил не меньше need. Например, для дела [4, 9] при запасе 8 за него не взяться, а при запасе 10 его можно сделать, и останется 6. Дела можно выполнять в любом порядке. Верните наименьший начальный запас сил, с которым удастся сделать все дела.
Пример 1
chores=[[3, 5], [4, 9], [1, 2]] → 9

С запасом 9 начинаем с дел, где нужен большой запас: [4, 9] оставляет 5, [3, 5] — 2, [1, 2] — 1. С запасом 8 не сработает никакой порядок: за дело [4, 9] так и не взяться.

Пример 2
chores=[[5, 5], [2, 8]] → 8

Если сначала [5, 5], к делу [2, 8] надо подойти с 8, значит старт 13. Если сначала [2, 8], нужно лишь max(8, 2 + 5) = 8.

Пример 3
chores=[[6, 6]] → 6
Ограничения
  • 1 ≤ len(chores) ≤ 10⁵
  • 1 ≤ cost ≤ need ≤ 10⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНаращиваем капитал проектами СложнаяРазличимые сокращения слов СложнаяБольше заказов к сроку СложнаяСамый узкий отрезок для всех списков СложнаяПо две отметки на отрезок Сложная
загружаем Python…
Вход
chores=[[3, 5], [4, 9], [1, 2]]
Ожидается
9

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 103 теста на сервере, включая скрытые.