Аудитории для лекций
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
3.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
В университете n лекций: i-я идёт с момента sᵢ до момента eᵢ, причём в момент eᵢ аудитория уже свободна (то есть лекция занимает промежуток [sᵢ, eᵢ)). Для каждой лекции нужна отдельная аудитория. Сколько аудиторий нужно, чтобы провести все лекции?
Формат ввода
В первой строке дано n. Далее n строк с парой sᵢ, eᵢ.
Формат вывода
Выведите минимальное число аудиторий.
Ограничения
1 ≤ n ≤ 2 · 10⁵, 0 ≤ sᵢ < eᵢ ≤ 2 · 10⁹.
Примеры
Пример 1
Ввод:
3
0 30
5 10
15 20
Вывод:
2
Пример 2
Ввод:
2
1 3
3 5
Вывод:
1
Комментарии