Urgence réseau – Épreuve régionale 2010

É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.