Максимальное количество непересекающихся отрезков
Дано
n отрезков вида [l; r], где обе границы включаются. Необходимо найти максимально возможное число отрезков, которые не пересекаются.Обратите внимание: если отрезки имеют совпадающие граничные точки, они не считаются пересекающимися.
Входные данные
В первой строке содержится одно целое число
n (1 ≤ n ≤ ) — количество отрезков.В следующих
n строках приведены два целых числа и ( ), разделённые пробелом.Выходные данные
Программа должна вывести максимальное количество непересекающихся отрезков.
Примеры
Входные данные | Выходные данные |
3
3 5
2 4
4 8 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB