На числовой прямой даны \(n\) отрезков. Требуется разбить
их на минимальное число групп так, чтобы внутри каждой группы любые два отрезка
не пересекались. При этом стыковка концом-к-началу пересечением
не считается: отрезки \([a, b]\) и
\([b, c]\) могут попасть в одну группу.
Найдите минимальное возможное число групп.
Формат входных данных
В первой строке — целое число \(n\)
(\(1 \le n \le 10^5\)).
В каждой из следующих \(n\) строк — два целых числа
\(l_i\) и \(r_i\)
(\(0 \le l_i < r_i \le 10^9\)) — концы очередного отрезка.
Формат выходных данных
Одно целое число — минимум групп.
Примечание
В первом примере отрезки \([0, 30]\),
\([5, 10]\), \([15, 20]\),
\([25, 35]\). В одну группу можно положить
\([5, 10]\), \([15, 20]\) и
\([25, 35]\) — они попарно не пересекаются. Отрезок
\([0, 30]\) пересекается с каждым из них и требует
отдельной группы. Итого: \(2\).
Во втором примере отрезки \([10, 20]\) и
\([20, 30]\) стыкуются по точке \(20\),
и по условию это не считается пересечением. Поэтому одной группы достаточно.
| № | Входные данные | Выходные данные |
|
1
|
4
0 30
5 10
15 20
25 35
|
2
|
|
2
|
2
10 20
20 30
|
1
|