Bartolomeo Pestalozzi, fondatore, proprietario e padrone della Premiata Ditta Pestalozzi & C. (con sede a Pisa) è disperato perché deve abbandonare per un certo periodo la sua ditta: si fida così poco dei suoi operai che si è fatto trasferire la scrivania direttamente nell'officina in modo da poter tenere costantemente tutto sotto controllo.
La situazione è complicata dal fatto che i turni degli operai sono estremamente irregolari. Più precisamente: sono dati N intervalli di tempo, ciascuno dei quali corrisponde a un turno (cioè alla presenza continuativa di un operaio 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.
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:
Il file di output, di nome output.txt, contiene un solo intero M, che deve soddisfare le seguenti proprietà:
L'esempio che segue è quello mostrato in figura:
| File input.txt | File output.txt |
8 0 3 1 6 2 5 4 9 7 8 10 12 11 14 13 15 | 3 |