Задачи
Отрезки
Отрезки
Даны отрезки на прямой. Какое максимальное количество отрезков можно выбрать так, чтобы никакие два из них не пересекались? Отрезки считаются открытыми.
Входные данные
В первой строке задано количество отрезков n~(1 \le n \le 10^5). В следующих n строках описаны отрезки: i-ая строка содержит два целых числа l_i и r_i~(1 \le l_i < r_i \le 10^9) — координаты начала и конца отрезка.
Выходные данные
Выведите максимальное количество непересекающихся отрезков.
Пример
Входные данные #1
5 1 4 3 8 7 8 2 5 4 6
Выходные данные #1
3
Входные данные #2
4 1 3 2 6 1 8 2 5
Выходные данные #2
1