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

Задача

Сколько нужно залов

жадность расписание куча сортировка наука и физика

Даны n встреч, каждая — полуинтервал [s, e): начинается в момент s и заканчивается в момент e, так что встреча, которая начинается ровно тогда, когда другая закончилась, может занять тот же зал. Какое наименьшее число залов нужно, чтобы провести все встречи, и как их разместить?

Третий и четвёртый тесты — все землетрясения силой от пяти баллов за 2015–2025 годы из каталога USGS. На каждое заводится дежурство: час для магнитуды 5, и с каждой следующей единицей магнитуды вдвое дольше (в четвёртом тесте — в шесть раз длиннее). Сколько дежурных бригад должно быть, чтобы ни одно событие не осталось без своей?

Вход

В первой строке n (1 ≤ n ≤ 2·10⁵), дальше n строк с целыми s и e (0 ≤ s < e ≤ 2·10⁹).

Выход

В первой строке — наименьшее число залов k. Во второй — n чисел от 1 до k: номер зала для каждой встречи в порядке входа. Если правильных размещений несколько, выведите любое.

Примеры

Пример 1

Вход
6
9 10
9 12
10 11
11 13
12 14
13 15
Выход
2
1 2 1 1 2 1

Ограничения

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

Разбор

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

1Подсказка 1

Нижняя граница видна сразу: если в какой-то момент идут одновременно d встреч, залов не меньше d. Попробуйте найти размещение, которому хватает ровно столько.

2Идея

Идём по встречам в порядке начала. Очередной встрече отдаём любой зал, который уже освободился, а если свободного нет — открываем новый. Залы, которые заняты, держим в куче по моменту освобождения: самый ранний — сверху.

3Разбор

Почему залов выйдет ровно столько, сколько встреч идёт одновременно в самый загруженный момент? Новый зал открывается, только когда все уже открытые заняты. Пусть это k-й зал, открытый для встречи, начинающейся в момент s. Каждая из k − 1 занятых встреч началась не позже s (мы идём по началам) и кончается позже s (иначе её зал был бы свободен). Значит, в момент s идут k встреч одновременно, и меньше k залов не хватит. Это типичный приём для жадности: жадный ответ совпал с нижней границей, и лучше быть не может.

Аккуратнее с границей: интервалы полуоткрытые, поэтому зал, который освобождается в момент s, уже можно отдать встрече, начинающейся в s. Из кучи забираем все залы с концом не позже s.

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

Сортировка — O(n log n), каждая встреча один раз входит в кучу и один раз выходит: всего O(n log n).

5Типичные ошибки
  • Касание считать пересечением. Встреча [10, 11) не мешает встрече [9, 10). Пример из условия ломается ровно на этом: правильный ответ — 2 зала.
  • Идти по концам, а не по началам. Для выбора наибольшего числа встреч в одном зале сортируют по концу, а здесь — по началу; спутать задачи легко.
  • Считать только число. Число залов находится и простым проходом по событиям «начало — конец», но размещение по залам требует кучи свободных залов.

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

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