Bridge Building
In dieser Stadt fließt ein wunderschöner Fluss direkt durch das Zentrum. Die Stadtverwaltung hat beschlossen, Brücken zu bauen, um die beiden Teile der Stadt miteinander zu verbinden. Zurzeit nutzen die Menschen Boote, um den Fluss zu überqueren, was jedoch nicht besonders praktisch ist.
Die Stadt hat
n mögliche Koordinatenpaare ermittelt, die per Brücke verbunden werden könnten. Allerdings gibt es die Auflage, dass sich die Brücken nicht gegenseitig kreuzen dürfen (eine Brücke darf nicht über eine andere geführt werden). Sie dürfen jedoch denselben Start- oder Endpunkt haben.Auf Grundlage der vorgeschlagenen Koordinatenpaare soll ermittelt werden, wie viele Brücken maximal gebaut werden können, ohne gegen diese Vorgabe zu verstoßen.
🌊
Die Koordinaten:
Man kann sich den Fluss als die OX-Achse in einem Koordinatensystem vorstellen.
Die beiden Stadtteile liegen also ober- und unterhalb der X-Achse. Die Koordinaten geben den
x-Wert für den Beginn bzw. das Ende einer Brücke an.Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ 100 000).Die nächsten
n Zeilen enthalten jeweils zwei ganzzahlige Werte , die mögliche Koordinaten für eine Brücke repräsentieren (1 ≤ ≤ ).Ausgabe
Das Programm soll eine einzelne ganze Zahl ausgeben: die maximale Anzahl der Brücken, die unter Einhaltung der Vorgaben gebaut werden können.
Beispiele
Eingabe | Ausgabe |
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