Maximale Anzahl nicht überschneidender Segmente
Gegeben sind
n Segmente der Form [l; r], bei denen beide Endpunkte inklusive sind. Die Aufgabe besteht darin, die maximale Anzahl solcher Segmente zu finden, die sich nicht überschneiden.Beachte, dass Segmente, deren Endpunkte dieselben Koordinaten aufweisen, nicht als überschneidend betrachtet werden.
Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ ), die die Anzahl der Segmente angibt.Die folgenden
n Zeilen enthalten jeweils zwei durch ein Leerzeichen getrennte ganze Zahlen und .Ausgabe
Das Programm soll die maximale Anzahl nicht überschneidender Segmente ausgeben.
Beispiele
Eingabe | Ausgabe |
3
3 5
2 4
4 8 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB