Сколько аудиторий нужно кружкам

В школе в один день проходит много занятий кружков. Для каждого занятия известно время начала и время конца (в минутах от 0 до 1\u00a0000\u00a0000).

Если два занятия идут одновременно, им нужны разные аудитории. Если одно занятие заканчивается ровно в минуту X, а другое начинается ровно в минуту X, то они не пересекаются и могут пройти в одной аудитории.

Нужно понять, какое минимальное число аудиторий достаточно, чтобы провести все занятия.

Формат ввода:

• В первой строке целое число n (1 \u2264 n \u2264 20000) \u2014 количество занятий.
• Далее n строк: по два целых числа s_i и e_i \u2014 начало и конец занятия.

Формат вывода:

• Выведите одно целое число \u2014 минимальное число аудиторий.

Ограничения:

• 0 \u2264 s_i < e_i \u2264 1\u00a0000\u00a0000
• Время занятия понимается как полуинтервал [s_i, e_i): минута e_i уже не занята.

Пример: Ввод:

5
0 10
10 20
5 15
15 25
7 8

Вывод:

3

Ключевое наблюдение: нам не важно, какая аудитория кому досталась. Важно только, сколько занятий одновременно активны. Тогда ответ — это максимум по времени числа «текущих» интервалов.

Приём: сканирующая прямая (sweep line). Мы превращаем каждый интервал [s, e) в два события: «началось» и «закончилось». Идём по событиям слева направо, поддерживаем счётчик активных занятий cur, и берём максимум best.

Почему работает: каждый раз, когда начинается занятие, нужна ещё одна аудитория (cur += 1), а когда заканчивается — аудитория освобождается (cur -= 1). Максимальное значение cur за весь проход и есть минимально достаточное число аудиторий.

План решения:

• Считать все пары (s, e).
• Сформировать список событий: (s, +1) и (e, -1).
• Отсортировать события по времени.
• Очень важно для одинакового времени: сначала конец, потом начало, потому что [s, e) не включает момент e. Удобная сортировка: events.sort(key=lambda x: (x[0], x[1])), ведь -1 < +1.
• Пройти по событиям: cur += delta, обновлять best = max(best, cur).
• Вывести best.

Сложность: сортировка 2n событий — O(n log n), проход — O(n).

Частая ошибка: перепутать порядок событий при одинаковом времени (если обработать старт раньше конца, получится лишняя аудитория, хотя занятие, закончившееся в X, уже освободило комнату для занятия, начинающегося в X).