Строительство мостов
В самом центре города протекает красивая река, и городские власти решили построить мосты, чтобы соединить разные части города. В настоящее время местные жители используют лодки для пересечения реки, что довольно неудобно.
Власти определили
n пар координат, которые потенциально можно соединить мостом. При этом существует условие, что мосты не должны пересекаться (один мост не может проходить над другим). Однако допускается, чтобы мосты начинались или заканчивались в одних и тех же точках.Задача — используя заданные пары координат, определить, какое максимальное количество мостов можно построить, не нарушая эти условия.
🌊
Координаты:
Можно рассматривать реку как ось OX в системе координат.
Две части города находятся выше и ниже оси X. Соответственно, координаты задают
x-координату начала/конца моста.Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ 100 000).В следующих
n строках приведены пары целых чисел , которые обозначают координаты, подлежащие соединению мостом (1 ≤ ≤ ).Выходные данные
Необходимо вывести одно целое число — максимальное количество мостов, которое можно построить при соблюдении всех требований.
Примеры
Входные данные | Выходные данные |
4
2 6
5 4
8 1
10 2 | 2 |
6
1 3
2 4
3 5
4 6
5 1
6 2 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB