CS
Задачник Базовый курс EN

Задача

Сколько успеть к сроку

расписание жадность куча сортировка классика олимпиады

У типографии один станок и n заказов. Заказ i занимает станок pi часов подряд и обещан к часу di, считая от начала работы. Станок начинает в момент 0, делает заказы по одному без перерывов, а порядок выбирает типография. Заказ сделан вовремя, если он закончен не позже своего срока; опоздавший заказ всё равно делается, но потом, и сколько он опоздал, неважно.

Сколько заказов наибольшее можно сделать вовремя?

Вход

В первой строке — число заказов n (1 ≤ n ≤ 105). Дальше n строк «pi di»: 1 ≤ pi ≤ 106, 1 ≤ di ≤ 1011.

Выход

Одно число — наибольшее число заказов, сделанных вовремя.

Первый пример — восемь заказов из статьи: вовремя можно сделать семь, если плакаты отложить на конец. Во втором пятичасовой заказ сделать вовремя можно, но тогда опоздают два из трёх часовых, а если его отложить, успевают все три.

Примеры

Пример 1

Вход
8
4 6
2 5
4 14
1 3
5 19
2 9
3 11
1 16
Выход
7

Пример 2

Вход
4
5 5
1 6
1 6
1 6
Выход
3

Ограничения

Время · Python
3000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
11 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Пусть уже решено, какие заказы делать вовремя. В каком порядке их выполнять, чтобы проверить, что все успевают? А если в этом порядке какой-то заказ опаздывает, от какого из уже взятых выгоднее всего отказаться?

2Идея

Набор заказов можно сделать вовремя тогда и только тогда, когда его успевает порядок по сроку: это правило Джексона из статьи о жадных алгоритмах — если наибольшее опоздание в порядке по сроку ноль, оно ноль, а меньше не бывает. Поэтому идём по заказам в порядке сроков и набираем их. Как только очередной заказ опоздал, кто-то из взятых, включая его самого, должен уйти — все они вместе не помещаются в его срок. Уходит самый долгий: он освобождает больше всего времени, и всё взятое снова успевает. Почему это не хуже любого другого выбора — доказано в статье: обмен «вместо любого выброшенного выбросить самый долгий» ничего не портит.

3Разбор

Сортируем заказы по сроку. Держим сумму часов взятых заказов t и кучу их длительностей с наибольшей наверху. Берём очередной заказ: кладём его длительность в кучу и прибавляем к t. Если t превысило срок этого заказа, достаём из кучи наибольшую длительность и вычитаем её из t. Одного выбрасывания хватает: самый долгий не короче только что взятого, а без нового заказа всё успевало. В конце размер кучи — ответ.

Сумма длительностей доходит до 1011: в Go нужен 64-битный int.

3+Решение
4Сложность

O(n log n): сортировка и не больше двух операций с кучей на заказ.

5Типичные ошибки
  • Брать, только если помещается. Тогда при опоздании выбрасывается новый заказ, а не самый долгий. Второй пример: пятичасовой заказ остаётся, а три часовых теряются.
  • Короткие сначала. Порядок по длительности не смотрит на сроки и проигрывает уже на первом примере.
  • Забыть вычесть. Выброшенный заказ уходит в конец и больше не занимает станок до сроков остальных; если не вычесть его часы из t, следующие заказы будут опаздывать зря.

Алгоритмы задачи

SYS Алгоритм Планирование задач Порядок работы: короткие сначала, сроки, прерывания, много ядер и аномалии Грэма. O(n log n): сортировка или куча 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи
Каталог алгоритмов