Na matfyze sa v budúcom semestri bude prednášať $n$ prednášok. Každá už má presne stanovený čas začiatku a konca (zadané ako celé čísla $z_i$ a $k_i$). Taktiež pre jednoduchosť predpokladajme, že každá prednáška môže byť robená v ľubovoľnej miestnosti.
Samozrejme, dve prednášky nesmú byť v tej istej miestnosti, ak sa ich intervaly časov prekrývajú. (Každá prednáška je uzavretý interval. Za prekryv sa teda počíta aj to, ak v nejakom okamihu jedna z prednášok začína a druhá končí.)
Nájdite najmenší možný počet prednáškových miestností, ktorý stačí na to, aby mohli (po vhodnom rozmiestnení do nich) prebehnúť úplne všetky dané prednášky.
Pre jednoduchosť nám bude stačiť, keď zistíte optimálny počet miestností. Netreba už zostrojiť a vypísať konkrétne rozmiestnenie prednášok do miestností.
V prvom riadku je číslo $n$: počet prednášok. Nasleduje $n$ riadkov a v každom z nich dve celé čísla popisujúce jednu prednášku: čas jej začiatku $z_i$ a čas jej konca $k_i$.
Počet prednášok v žiadnom testovacom prípade neprekročí $200 000$. Časy sú z rozsahu od $0$ do $2 \cdot 10^9$.
Vypíšte jeden riadok a v ňom jedno celé číslo: najmenší možný počet posluchární.
2
10 20
20 30
2
Prednášky sa prekrývajú, musia teda byť v rôznych miestnostiach.
2
21 30
10 20
1
Prednášky sa neprekrývajú, môžu teda byť v tej istej miestnosti.
4
30 70
20 80
72 95
65 73
3
Prvá a po nej tretia prednáška bude v posluchárni A, druhá v posluchárni B a štvrtá v posluchárni C.