← вернуться к уроку · Практика: Жадные идеи и их ловушки
Платформы с уборкой
5000 мс · 256 МБ · всё или ничего
На станции поездов: поезд прибывает в момент и отправляется в момент . После отправления платформу убирают ещё минут, и всё это время она занята.
То есть платформа свободна для нового поезда только начиная с момента . Какое наименьшее число платформ нужно станции?
Формат ввода
В первой строке числа от до и от до . Во второй — чисел: пары и подряд, .
Формат вывода
Одно число.
Примеры
ввод
3 1 1 5 2 6 7 8
вывод
2
Примечание
Уборка не требует нового алгоритма: достаточно считать, что поезд занимает платформу до момента .
Войдите, чтобы отправлять решения.