Maximum de segments sans intersection
Étant donné
n segments de la forme [l; r], dont les deux bornes sont inclusives, il vous est demandé de déterminer le nombre maximal de segments qui n’ont aucune intersection.Notez que si deux segments partagent exactement les mêmes bornes, ils ne sont pas considérés comme se recoupant.
Entrée
La première ligne de l’entrée contient un seul entier
n (1 ≤ n ≤ ) – le nombre de segments.Les
n lignes suivantes contiennent deux entiers séparés par un espace, et .Sortie
Le programme doit afficher le nombre maximal de segments qui ne se recoupent pas.
Exemples
Entrée | Sortie |
3
3 5
2 4
4 8 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB