Máximo de segmentos não intersetados
Dado
n segmentos no formato [l; r], em que ambas as extremidades são inclusivas, pretende-se determinar o número máximo de segmentos que não se intersectam.Note que segmentos cujos extremos coincidam exatamente não são considerados como tendo interseção.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ), que representa a quantidade de segmentos.As próximas
n linhas contêm dois inteiros separados por espaço, e .Saída
O programa deve imprimir o número máximo de segmentos que não se intersectam.
Exemplos
Entrada | Saída |
3
3 5
2 4
4 8 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB