Prihlásenie Registrácia  

B - Projekty

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Gabriel si povedal, že chce viesť čo najviac projektov v nasledujúcom období (5-ročnici). Problém však je, že niektoré projekty sa konajú súbežne alebo sa termíny ich konania prekrývajú (a vedúcim môže byť len jedného projektu v čase). Ktoré projekty by si mal Gabo vybrať, ak chce viesť čo najviac? Poznamenajme, že ak sa Gabo rozhodne, že bude vedúcim nejakého projektu, tak ním bude po celú dobu trvania projektu. Ak teda projekt, ktorý bude viesť, končí v 10. mesiac, najbližší ďalší projekt, kde by mohol byť vedúcim, môže začínať až v 11. mesiac.

Úloha

Vytvorte program, ktorý pre zadanú množinu projektov vypočíta maximálny počet projektov, ktorých sa môže Gabo v nasledujúcom období zúčastniť.

Vstup

Prvý riadok vstupu obsahuje jedno prirodzené číslo N (1 ≤ N ≤ 80) vyjadrujúce počet projektov v nasledujúcom období. Nasleduje N riadkov s údajmi o jednotlivých projektoch. Každý projekt je popísaný dvojicou medzerami oddelených čísel: začiatočný mesiac a koncový mesiac. Začiatočný a koncový mesiac sú poradové čísla od aktuálneho mesiaca (t.j. mesiace sú označené ako 0, 1, 2, 3, ...,), t.j. začiatočný a koncový mesiac sú nezáporné čísla menšie ako 2000.

Výstup

Maximálny počet projektov, ktorých sa Gabriel môže zúčastniť ako vedúci.

Príklad

Vstup:

10
6 14
4 10
6 6
14 19
4 4
15 18
5 14
3 11
19 24
5 13

Výstup:

4