Allenamenti 2010

Controllare l'accampamento (padrun)

Difficoltà D = 1 romano. Tempo limite 2 sec.

Descrizione del problema

La vita non è facile nei quattro accampamenti fortificati di Laudanum, Petibonum, Baobarum e Aquarium, che circondano il villaggio dell'Armorica abitato da irriducibili galli. I centurioni hanno grandi difficoltà nel mantenere la disciplina delle proprie legioni, e sono costretti a tenere i propri soldati sotto strettissimo controllo.

La situazione è complicata dal fatto che i turni dei soldati sono estremamente irregolari. Più precisamente: sono dati N intervalli di tempo, ciascuno dei quali corrisponde a un turno (cioè alla presenza continuativa di un soldato per quell'intervallo di tempo); dovete stabilire il minor numero possibile di turni da scegliere in modo tale che ogni altro turno sia coperto almeno in parte da uno dei turni scelti.

Dati di input

Il file di input, di nome input.txt, contiene sulla prima riga un intero N, che è il numero dei turni. Su ciascuna delle successive N righe ci sono due interi non negativi a e b, separati da uno spazio, che corrispondono a un intervallo di tempo [a, b]. Più precisamente, potete assumere che:

Dati di output

Il file di output, di nome output.txt, contiene un solo intero M, che deve soddisfare le seguenti proprietà:

Assunzioni

Esempi di input/output

L'esempio che segue è quello mostrato in figura:

File input.txtFile output.txt
8
0 3
1 6
2 5
4 9
7 8
10 12
11 14
13 15
3