Крыша из плит
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Нужно закрыть крышей участок от 0 до L. Есть n плит, плита — отрезок [lᵢ, rᵢ]. Плиты можно накладывать друг на друга, стыковка в одной точке допустима. Какое наименьшее число плит нужно, чтобы закрыть весь участок? Если нельзя — выведите -1.
Формат ввода
В первой строке даны n и L. Далее n строк с парой lᵢ, rᵢ.
Формат вывода
Выведите минимальное число плит или -1.
Ограничения
1 ≤ n ≤ 2 · 10⁵, 1 ≤ L ≤ 10⁹, 0 ≤ lᵢ ≤ rᵢ ≤ L.
Примеры
Пример 1
Ввод:
3 10
0 4
3 8
6 10
Вывод:
3
Пример 2
Ввод:
2 10
0 3
5 10
Вывод:
-1
Комментарии