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

Задача

Кратчайший остаток

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

На сервер проверки приходят n сдач. Сдача i приходит в момент ri и требует pi миллисекунд работы ядра. Ядро одно и в каждый момент работает над одной сдачей, но может в любой момент прервать её, заняться другой и потом вернуться: сделанное не теряется, и переключение ничего не стоит. Начать сдачу раньше её прихода нельзя. Время оборота сдачи — от прихода до момента, когда её работа закончена.

Найдите наименьшую возможную сумму времён оборота всех сдач. Среди тестов — все тесты задач каталога с настоящим временем эталонных решений, приходящие в случайные моменты.

Вход

В первой строке — число сдач n (1 ≤ n ≤ 105). Дальше n строк «ri pi» в любом порядке: 0 ≤ ri ≤ 1011, 1 ≤ pi ≤ 106. Несколько сдач могут прийти в один момент.

Выход

Одно число — наименьшая сумма времён оборота.

В первом примере пятимиллисекундная сдача начинается сразу, но в моменты 1 и 2 приходят короткие: если прерываться ради них, у каждой время оборота 1 мс, а длинная заканчивается в момент 7 — всего 9. Без прерываний вышло бы 5 + 5 + 5 = 15. Во втором примере ядро стоит с момента 6 до 10, а сдача, пришедшая в момент 4, приходит ровно тогда, когда заканчивается первая.

Примеры

Пример 1

Вход
3
0 5
1 1
2 1
Выход
9

Пример 2

Вход
5
10 3
0 4
4 2
10 1
13 2
Выход
14

Ограничения

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

Разбор

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

1Подсказка 1

Если бы все сдачи пришли сразу, лучшим был бы порядок «короткие сначала». Что меняется, когда сдачи приходят по одной? Что известно о сдаче, которую ядро делает сейчас, в момент прихода новой?

2Идея

Работать всегда надо над той сдачей, которой осталось меньше всего, и прерывать её, если пришла сдача с ещё меньшим остатком. Это правило SRPT, и в статье доказано, что сумма времён оборота у него наименьшая: если в какой-то момент работают над сдачей j, хотя у сдачи i остаток меньше, поменяем местами их будущую работу — сначала доделаем i в тех же промежутках времени. Сдача i закончится не позже, чем раньше заканчивалась первая из двух, а j — тогда же, когда раньше вторая, так что сумма не выросла.

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

3Разбор

Сортируем сдачи по моменту прихода. Держим кучу пар «остаток, номер» и текущее время t. Если куча пуста, перескакиваем к следующему приходу. Кладём в кучу всё, что пришло к t, и берём сдачу с наименьшим остатком. Если она успевает закончиться до следующего прихода, заканчиваем её и прибавляем к ответу её время оборота. Иначе работаем над ней до следующего прихода, уменьшаем остаток и кладём её обратно.

Каждый приход прерывает работу не больше одного раза, поэтому событий O(n). Сумма доходит до 1016 — в Go нужен 64-битный int.

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

O(n log n): сортировка и O(n) операций с кучей.

5Типичные ошибки
  • Без прерываний. «Короткая следующей» хороша, пока все пришли разом, а когда приходят по одной, длинная, начатая чуть раньше, держит всех. Первый пример: 15 вместо 9.
  • Сравнивать полную длину, а не остаток. Почти сделанная длинная сдача короче по остатку, чем новая средняя, и прерывать её ради новой — потеря.
  • Шагать по миллисекундам. Ответ тот же, но моменты доходят до 1011: шагать надо от события к событию.

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

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