Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Lomamökki


Task | Statistics


CSES - LomamökkiCSES - Lomamökki

Time limit:1.00 s Memory limit:512 MB

Sinulla on lomamökki, jota vuokraat asiakkaille. Tiettynä päivänä mökissä voi olla enintään yksi asiakas.

Luoksesi tulee tietyssä järjestyksessä $n$ asiakasta, joista jokainen haluaa vuokrata mökin päivästä $a$ päivään $b$. Kuka on ensimmäinen asiakas, jonka toivomusta et pysty toteuttamaan?

Huomaa, että jos asiakas poistuu mökistä päivänä $k$, seuraava asiakas voi saapua aikaisintaan päivänä $k+1$.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: asiakkaiden määrä. Asiakkaat on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $n$ riviä, joista jokaisella on kaksi kokonaislukua $a$ ja $b$: asiakas haluaa vuokrata mökin päivästä $a$ päivään $b$.

Tuloste

Tulosta yksi kokonaisluku: ensimmäinen asiakas, jonka toivomusta et voi toteuttaa. Jos voit toteuttaa kaikki toivomukset, tulosta kuitenkin $-1$.

Rajat
Esimerkki 1

Syöte:
4
2 5
8 9
3 7
12 15


Tuloste:
3

Selitys: Asiakas 3 haluaa vuokrata mökin päivästä 3 päivään 7. Tämä ei kuitenkaan onnistu, koska asiakas 1 on jo vuokrannut mökin päivästä 2 päivään 5.