Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Hotelli

Hotelli


View task | Model solution | Statistics


Hotelli

Time limit:1.00 s
Memory limit:512 MB

Hotelliin on tulossa lähiaikoina $n$ asiakasta, joista jokainen majoittuu yhdessä huoneessa.

Tiedät jokaisen asiakkaan tulo- ja lähtöpäivän. Kaksi asiakasta voi majoittua samassa huoneessa, kunhan ensimmäisen asiakkaan lähtöpäivä on aiemmin kuin toisen asiakkaan tulopäivä.

Mikä on pienin määrä huoneita, joka riittää kaikkien asiakkaiden majoittamiseen? Entä miten huoneet voi jakaa käytännössä?

Syöte

Syötteen ensimmäisellä rivillä on yksi kokonaisluku $n$: asiakkaiden määrä.

Sitten syötteessä on $n$ riviä, joista jokainen kuvaa yhden asiakkaan. Kullakin rivillä on kaksi kokonaislukua $a$ ja $b$: asiakkaan tulo- ja lähtöpäivä.

Tuloste

Tulosta ensin yksi kokonaisluku $k$: pienin tarvittavien huoneiden määrä.

Tulosta sitten rivi, jossa on jokaisen asiakkaan huoneen numero samassa järjestyksessä kuin syötteessä. Huoneet on numeroitu $1,2,\ldots,k$.

Rajat
Esimerkki

Syöte:
3
1 2
2 4
4 4


Tuloste:
2
1 2 1