Massimo numero di segmenti non intersecanti
Dato
n segmenti della forma [l; r], con entrambi gli estremi inclusi, si desidera calcolare il massimo numero di segmenti che non si intersecano.Ricorda che, se due segmenti condividono esattamente gli estremi, non vengono considerati come intersecanti.
Input (Dati in ingresso)
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ), che rappresenta il numero di segmenti.Le successive
n righe contengono due numeri interi separati da uno spazio, e ().Output (Dati in uscita)
Il programma deve stampare il massimo numero di segmenti che non si intersecano.
Esempi
Input | Output |
3
3 5
2 4
4 8 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB