Расписание кабинета
Условие
В школе один и тот же кабинет хотят занять разные кружки. Каждый кружок прислал время начала и конца занятия.
Кабинет можно быстро проветрить, поэтому если одно занятие заканчивается ровно в момент, когда другое начинается, они не мешают друг другу.
Нужно понять, сколько занятий максимум можно провести в этом кабинете за день, если выбрать подходящий набор кружков.
Формат ввода
В первой строке дано целое число n — количество заявок. Далее в n строках даны по два целых числа s и t — начало и конец занятия.
Считайте, что занятие занимает кабинет на полуинтервале [s, t), то есть момент t уже свободен.
Формат вывода
Выведите одно целое число — максимальное количество занятий, которые можно провести, не накладывая их друг на друга.
Ограничения
1 ≤ n ≤ 120000 ≤ s < t ≤ 1000000
Пример
Ввод:
5
1 4
3 5
0 6
5 7
8 9Вывод:
3Как решать — идея подхода
Приём: Жадный выбор по времени окончания
Ключевое наблюдение: если мы хотим провести как можно больше занятий без пересечений, «опаснее всего» оставлять кабинет занятым надолго. Поэтому среди всех занятий, которые можно поставить первыми, выгоднее выбрать то, которое заканчивается раньше всех — тогда мы оставим максимум места для остальных.
Почему работает жадность: пусть мы уже выбрали несколько занятий и ищем следующее. Если взять занятие с более поздним концом, оно только уменьшит число вариантов дальше. Замена на занятие с более ранним концом не ухудшает ответ, потому что оно освобождает кабинет раньше.
План решения:
- Считай все пары (s, t).
- Отсортируй занятия по t (время конца) по возрастанию (при равных t порядок не важен).
- Иди по отсортированному списку и храни
last_end— конец последнего выбранного занятия. - Если текущее занятие начинается не раньше, чем
last_end, то выбирай его:if s >= last_end: ans += 1; last_end = t. - Выведи
ans.
Важно про полуинтервал [s, t): занятие, которое начинается ровно в момент окончания предыдущего, совместимо, поэтому условие именно s >= last_end, а не s > last_end.
Сложность: сортировка O(n log n), проход O(n). При n до 12000 это быстро.
Частая ошибка: сортировать по началу s (или выбирать самое короткое по длительности) — это ломает оптимальность; критично сортировать именно по времени окончания.
Разберись руками
Есть 5 кружков: [1,4), [3,5), [0,6), [5,7), [8,9). Если один заканчивается ровно в момент старта другого, то они совместимы (например, конец 4 и старт 4 — ок). Нужно выбрать максимум занятий без пересечений.
- Попробуем наивно: «беру то, что начинается раньше всех». Какое занятие тогда возьмёшь первым?
- После [0,6) какое из оставшихся можно поставить СЛЕДУЮЩИМ (чтобы не было наложения)?
- Попробуем другой ход: чтобы оставить больше места дальше, какое занятие выгоднее взять первым — то, которое заканчивается раньше. Какое здесь заканчивается раньше всех?
- Прогоним идею «самый ранний конец» на всём примере. Представь, что занятия уже отсортированы по времени конца: [1,4), [3,5), [0,6), [5,7), [8,9). Состояние будем писать так: "до_какого_момента_занято, сколько_взяли". Старт: "-1,0". После каждого занятия решай: берём (если начало не раньше свободного момента) или пропускаем.
Идея: Если хочешь уместить как можно больше занятий, сначала выбирай то, которое заканчивается раньше всех, потом снова среди оставшихся выбирай самое раннее по концу, но бери его только если оно не пересекается с уже выбранным (можно стартовать ровно в момент окончания). Так ты освобождаешь кабинет как можно раньше и оставляешь больше шансов для следующих.
Решить задачу с автопроверкой на Python →
Куда дальше
- Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели
- Олимпиада по информатике: с чего начать — два мира олимпиад — ВсОШ и перечневые: этапы, задания и на каком языке писать
- На программиста по олимпиаде: путь по классам — что даёт диплом, куда с ним берут на ИТ-направления и почему решает 9 класс