Zadanie

V Mandarínsku žije samoľúby král Nenásytnan Veľký, ktorý má rád mandarínky. Má ich až tak rád, že každý deň počas mandarínkovej sezóny jednu zje1. A keďže on je veľmi nenástytný tak každý deň musí zjesť tú najväčšiu čo sa v predchádzajúci deň v Mandarínsku urodila. V Mandarínsku počas sezóny narastie každý deň \(n\) mandariniek. Tieto mandarínky sa potom rovnomerne poukladajú na jednu dlhú linku, kde ich manuálne zoraďujú pracovníci od najmenšej po najväčšiu s cieľom aby sa najväčšia mandarínka dostala priamo na kráľovský stôl. Každý pracovník je zamestnaný na určitom úseku linky a jeho úlhou je usporiadať mandarínky na linke podľa veľkosti v rámci jeho úseku (rozsahu rúk).

Keďže aj do Mandarínska prišla pandémia, z hygienických dôvodov sa môže na každom pracovisku nachádzať naraz iba jeden zamestnanec. Podľa nariadenia hlavného hygienika Mandarínska sú zamestnanci každý deň púšťaní do práce postupne podľa ich zamestnaneckého čísla. Každý z nich tam môže byť iba nevyhnutný čas a potom musí ísť domov.

Tento postup musí dodržiavať aj mandarínková triediaca linka. Šéf tejto linky Kleofáš Múdry rozmýšla ako ho najlepšie implementovať. Počas prvých dní pandémie do firmy púšťal všetkých zamestnancov postupne, tak ako to vyžaduje nariadenie. Potom si však uvedomil, že keďže jedinou úlohou celej linky je nájsť najväčšiu mandarínku a poslať ju ku kráľovi, možno by mohol ako dobrý šéf nechať niektorých svojich zamestnancov doma. Teraz rozmýšla nad tým koľko zamestnancov reálne musí chodiť do práce aby linka plnila to na čo bola určená. Viete mu s tým pomôcť?

Úloha

Na triediacej linke sa v pravidelných rozostupoch nachádza \(n\) mandaríniek. Vo firme pracuje \(m\) zamestnancov. Každý z nich príde do práce a podľa veľkosti vzostupne utriedi mandarínky na linke medzi \(a_i\)-tou a \(b_i\)-tou vrátane, pričom na linke udržiava pravidelné rozostupy. Kleofáš chce vybrať čo najmenej zamestnancov tak, aby vedel zaručiť že ak by prišli do práce iba oni, tak nech je najväčšia mandarínka na začiatku dňa na linke na ľubovolnom mieste, na konci dňa vždy skončí na pozícii \(n\). Zistite koľko najmenej zamestnancov musí vybrať do smeny. Nezabudnite že do práce musia prísť v poradí podľa zamestnaneckého čísla.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve celé čísla \(n,m\) (\(1 \leq n,m \leq 300\,000\)) – denná produkcia Mandarínska a počet zamestnancov na linke. Na ďaľších \(m\) riadkoch sa nachádzajú intervaly na ktorých pracujú jednotliví zamestnanci. Na \(i\)-tom riadku sa nachádzajú čísla \(a_i\) a \(b_i\) (\(1\leq a_i \leq b_i \leq n\)), kde \([a_i, b_i]\) je interval ktorý je triedený zamestnancom so zamestnaneckým číslom \(i\).

Formát výstupu

Na výstup vypíšte jediné číslo – minimálny počet zamestnancov, ktorý musia prísť do práce na to, aby sa najväčšia mandarínka zaručene dostala na poslednú pozíciu na triediacej linke. V prípade že je na triediacej linke už teraz taký zmätok, že aj bez vynechania zamestnanca sa najväčšia mandarínka nie nutne dostane ku kráľovi, vypíšte \(-1\).

Hodnotenie

Sú \(4\) sady vstupov. V jednotlivých sadách platia nasledovné obmedzenia:

  1. \(n \leq 10\), \(m \leq 10\)
  2. \(n \leq 100\), \(m \leq 100\)
  3. \(n \leq 300\,000\), \(m \leq 2\,000\)
  4. \(n \leq 300\,000\), \(m \leq 300\,000\)

Príklady

Input:

6 2
1 4
4 6

Output:

2

Obaja zamestnanci musia prísť do práce, inak by sa najväčšia mandarínka z pozície 3 nemohla dostať na koniec linky na pozíciu 6.

Input:

6 2
4 6
1 4

Output:

-1

V tomto prípade ak sa najväčšia mandarínka nachádza na pozícii 3 tak keď príde do práce prvý zamestnanec tak ju neposunie a druhý zamestnanec ju posunie iba na pozíciu č. 4. Aj keď prídu do práce všetci zamestnanci, najväčšia mandarínka na konci dňa nemusí byť na poslednej pozícii.

Input:

6 3
1 4
2 5
3 6

Output:

2

Stačí ak do práce príde iba prvý a tretí zamestnanec. Ak najväčšia mandarínka začínala medzi pozíciami 1 až 4, prvý zamestnanec ju umiestni na pozíciu 4. Tretí zamestnanec ju stadiaľ vie položiť na koniec, a zvláda aj prípad kedy mandarínka bola na začiatku na pozícií 5.

  1. Voľakedy ich jedol viac, ale to mu jeho diétny asistent zakázal, pretože sa nezmestil na kráľovskú fotografiu.↩︎

Pozrime sa na to, aké podmienky musí vybraná postupnosť zamestnancov spĺňať, aby sa najväčšia mandarínka dostala z ľubovoľnej začiatočnej pozície na poslednú. Pre jednoduchosť sa pozrime na prvú mandarínku a ako ona bude cestovať v rámci vybranej množiny zamestnancov.

Vždy, keď mandarínka prejde rukami nejakého zamestnanca, tým že je najväčšia sa ocitne na konci intervalu, ktorý má tento zamestnanec na starosti. Preto precestuje nejakou podpostupnosťou zamestancov až na koniec. Každý ďalší zamestnanec v tejto postupnosti sa prekrýva v pracovnom intervale s intervalom predchádzajúceho zamestnanca. Zároveň na to, aby druhý zamestnanec mandarínku vôbec zodvihol, musí jeho interval končiť až po konci predchádzajúceho intervalu. Posledný zamestnanec, ktorého rukami mandarínka prejde ju dá na posledné miesto. Všimnime si tiež, že táto postupnosť, ktorou prejde najväčšia mandarínka, je istým spôsobom minimálna. To znamená, že keby iba táto časť zamestancov prišla do práce, tak ľubovoľná mandarínka z ľubovoľnej pozície by sa dostala na koniec.

Toto sa dá dokázať tak, že sa paralelne pozrieme na dva prípady: Na to, keď je mandarínka na začiatku na prvej pozícii a na to, keď je na pozícii P. Ak mandarínka z pozície P neskončila na konci na správnej pozícii, tak musela skončiť skôr. Teda mandarínka z pozície 1 ju musela predbehnúť. Pozrime sa na moment, kedy ju predbehla. Zistíme, že v tom momente úradoval jeden konkrétny zamestnanec. Ten mandarínku začínajúcu na pozícii 1 presunul na koniec svojho intervalu, ale mandarínku začínajúcu na pozícii P nie. Toto je však spor, keďže mandarínka z pozície P je tiež najväčšia v tom svojom prípade.

Z tohto vyplýva, že hľadáme najkratšiu možnú postupnosť zamestnancov takú, aby sa prvá mandarínka vedela dostať na poslednú pozíciu. Musí teda spĺňať to, že v postupnosti sú zamestnanci, kde každý ďaľší sa v intervale práce prekrýva s predchádzajúcim a kde aj konce intervalov v poradí rastú.

Na to aby sme našli túto podmnožinu intervalov môžeme použiť dynamické programovanie. A to takým spôsobom, že si pre každú pozíciu budeme pamätať, na koľko najmenej skokov medzi intervalmi sa najväčšia mandarínka vie dostať z prvej pozície na túto. Na začiatku sa mandarínka vie dostať na prvú pozíciu na 0 skokov a na ostatné pozície na nekonečne veľa skokov (inými slovami, nevie sa tam dostať). Potom prichádzajú postupne zamestnanci. Každý zamestnanec môže najväčšiu mandarínku na koniec svojho intervalu preniesť až potom, čo najväčšia mandarínka do tohto intervalu vstúpi. Teda na koniec svojho intervalu do poľa zapíše minimum čísel nájdených v intervale plus jedna.

Priamočiara implementácia tejto myšlienky je taká, že si tieto hodnoty ukladáme do poľa. Potom pre každého zamestnanca nájdeme minimum intervalu ktorý mu prislúcha. Následne, ak je toto číslo menšie ako to, ktoré tam máme aktuálne napísané, tak ho prepíšeme. Na nájdenie minima môžme potrebovať spraviť \(O(n)\) krokov. Preto celkovo môže byť časová zložitosť až \(O(mn)\).

Lepším riešením môže byť napríklad použiť intervalový strom. Ten nám umožní zistiť minimum intervalu v čase \(O(log n)\). Tým sa nám zlepší časová zložitosť na \(O(m log n + n)\). Pamäťová zložitosť bude kvôli zamestnancom a intervalovému stromu \(O(n + m)\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.