Máximo de segmentos no intersectantes
Dado
n segmentos de la forma [l; r], donde ambos extremos son inclusivos, se solicita calcular el número máximo de segmentos que no se intersecan entre sí.Ten en cuenta que los segmentos que comparten sus puntos extremos no se consideran intersectantes.
Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ ), que representa la cantidad de segmentos.Las siguientes
n líneas contienen dos enteros separados por un espacio, y .Salida
El programa debe imprimir el número máximo de segmentos que no se intersecan.
Ejemplos
Entrada | Salida |
3
3 5
2 4
4 8 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB