На числовой прямой даны \(n\) отрезков. Нужно выбрать
минимальное количество точек на прямой так, чтобы каждый отрезок содержал
хотя бы одну из выбранных точек.
Точка \(x\) принадлежит отрезку
\([l, r]\), если \(l \le x \le r\)
(концы включены).
Формат входных данных
В первой строке — целое число \(n\)
(\(1 \le n \le 10^5\)).
В каждой из следующих \(n\) строк — два целых числа
\(l_i\) и \(r_i\)
(\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.
Формат выходных данных
Одно целое число — минимальное количество точек.
Примечание
В первом примере четыре отрезка: \([1, 6]\),
\([2, 8]\), \([7, 12]\),
\([10, 16]\). Точки \(x = 6\)
и \(x = 10\) вместе попадают в каждый из отрезков:
\(6\) — в первые два, \(10\) — в последние два.
Меньше двух точек не хватит — отрезки \([1, 6]\) и
\([10, 16]\) не пересекаются, одной общей точки у них нет.
Во втором примере все три отрезка содержат точку \(x = 5\),
так что одной точки достаточно.
| № | Входные данные | Выходные данные |
|
1
|
4
1 6
2 8
7 12
10 16
|
2
|
|
2
|
3
0 10
3 5
5 9
|
1
|