Urgence réseau – Regional event 2010

Level 4

ÉNONCÉ

Alerte !! Toutes les fibres optiques qui reliaient le nord et le sud de Paris étaient posées sur le lit de la Seine ; or, il y a quelques heures, une péniche a laissé traîner son ancre et les a toutes coupées !

On veut rétablir le plus vite possible le service ; on va donc essayer de reposer quelques fibres à la va-vite entre quelques points cruciaux. Il y a N fibres ; pour chacune, on vous donne l'abscisse le long du fleuve de son point d'arrivée sur la rive gauche, et de son point de départ sur la rive droite (eh oui, ils ne sont pas en face, la construction du réseau a été un peu chaotique...).

La réparation devant se faire au plus vite, on veut rendre le travail des ouvriers le plus simple possible ; les machines qui poseront la fibre sur le lit du fleuve ne devront donc pas se croiser en les posant. Combien de fibres pouvez-vous réparer au maximum sans qu'elles ne se croisent ?

ENTRÉE

  • N nombre de fibres, suivi de N lignes de 2 entiers : les abscisses de la fibre i sur les deux rives.

LIMITES

  • N <= 5000

SORTIE

  • Sur une seule ligne, le nombre maximum de fibres réparables.

Runtime constraints

Maximum memory usage
256 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4
1 3
2 5
3 1
6 6
Sample output
3
Sample input
6
1 3
7 4
6 7
2 5
3 2
4 5
Sample output
4

Submit your solution

You have to register or log in to be able to submit your solution.