Construction de ponts
Il existe une ville traversée en son centre par une magnifique rivière. La municipalité a décidé de construire des ponts pour relier les différentes parties de la ville. Jusqu’à présent, les habitants utilisaient des bateaux pour traverser la rivière, ce qui n’est pas très pratique.
La ville a identifié
n paires de coordonnées pouvant être reliées par un pont. Cependant, les autorités exigent que ces ponts ne se chevauchent pas (un pont ne peut pas en recouvrir un autre). Ils peuvent néanmoins partager leurs points de départ ou d’arrivée.Étant donné les paires de coordonnées possibles, vous devez déterminer le nombre maximal de ponts que la municipalité peut construire sans enfreindre ces règles.
🌊
Les coordonnées :
Vous pouvez considérer la rivière comme l’axe OX d’un système de coordonnées.
Les deux parties de la ville se trouvent au-dessus et au-dessous de l’axe des X. Par conséquent, les coordonnées correspondent à la valeur
x qui définit l’emplacement de chaque extrémité d’un pont.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000).Les
n lignes suivantes contiennent des paires d’entiers qui représentent les coordonnées pouvant être reliées (1 ≤ ≤ ).Sortie
Le programme doit afficher un seul entier : le nombre maximal de ponts que la municipalité peut construire.
Exemples
Entrée | Sortie |
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