1. Pohodový festival

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabe na

Leto sa blíži a s ním aj Sysľov obľúbený hudobný festival. Tak ako každý rok, aj teraz naň príde veľa skvelých kapiel, ktoré by si Syseľ rád vypočul. Bohužiaľ, nedá sa stihnúť všetko, pretože jednotlivé koncerty sa prekrývajú. Aby však maximalizoval svoj hudobný zážitok, chcel by ich Syseľ stihnúť čo najviac. Viete mu poradiť, ktorých koncertov sa má zúčastniť?

Úloha

Festival začína v čase 0 a uskutoční sa na ňom niekoľko koncertov. Každý koncert má pevne určený čas začiatku a čas konca. Samozrejme, každý koncert skončí neskôr ako začal a začiatok ani koniec sa nebudú posúvať¹. Inak sa však koncerty môžu ľubovoľne prekrývať.

Keď si Syseľ vyberie niektorý koncert, chce sa ho zúčasniť celého. Nemôže teda počas neho odísť na nejaký iný koncert. Ak však nejaké vystúpenie končí v ten istý čas ako začína iné, Syseľ vie stihnúť oba koncerty. Naviac nemá žiadne preferencie, takže jeho cieľom je naozaj iba maximalizovať počet koncertov, ktorých sa zúčastní.

Predstavme si, že na festivale sú 4 koncerty – koncert A začína v čase 1 a končí v čase 10, koncert B začína v čase 12 a končí v čase 17, koncert C začína v čase 6 a končí v čase 14 a koncert D začína v čase 17 a končí v čase 20. Vidíme, že najlepšie, čo vie Syseľ spraviť je ísť na koncerty A, B a D. Koncert C sa totiž prekrýva s koncertom A aj B a ak by naň Syseľ išiel, stihol by najviac jeden ďalší koncert (D).

1. (3 body) Syseľ sa rozhodol vyberať si koncerty nasledovným spôsobom – ako na prvý ide na koncert, ktorý začína čo najskôr. Následne vždy keď skončí koncert, na ktorom je, ponáhľa sa na koncert s najbližším začiatokm.

   V našom príklade teda ide na koncert A. Ten skončí v čase 10. Koncert C je vtedy v plnom prúde a Syseľ ho už nestíha. Najbližšie začína koncert B a Syseľ sa ho zúčastní. Keď v čase 17 skončí aj ten, Syseľ si všimne, že ešte stíha začiatok koncertu D a preto sa tam ponáhľa. Po konci koncertu D sa už žiaden ďalší nekoná a Syseľ ide domov.

   Takýto spôsob vyberania koncertov je však chybný. Vytvorte taký zoznam koncertov (s ich začiatkami aj koncami), že opísaný postup na nich nenájde najlepšie možné riešenie. Na vašom príklade tiež ukážte, aké riešenie nájde popísaný postup a vysvetlite, prečo toto riešenie nie je optimálne.

2. (4 body) Po neúspechu z podúlohy a) prišiel Syseľ s novou metódou. Najskôr si pre každý koncert vypočíta, s koľkými inými koncertami sa prekrýva. Následne si vyberie koncert s najmenším počtom prekryvov. Zo zoznamu koncertov vymaže tento vybraný koncert a aj všetky koncerty, s ktorými sa prekrýval (a ktorých sa teda nebude môcť zúčastniť). No a opísaný postup (aj s počítaním prekryvov) opakuje na zvyšných koncertoch, až kým ich všetky nevyškrtá.

   V našom príklade si teda spočíta, že koncerty A a B majú 1 prekryv, koncert D má 0 prekryvov (koncerty B a D sa neprekrývajú) a koncert C má 2 prekryvy. Vyberie si preto koncert D a vyhodí ho zo zoznamu koncertov (a iba ten, pretože sa s ničím neprekrýva). Ostali mu tri koncerty, s počtom prekryvov 1, 1 a 2.

   Keďže mu nezáleží na tom, ktorý z koncertov s 1 prekryvom si vyberie, vyberie si napríklad koncert A. Zo zoznamu koncertov teda musí vyhodiť koncert A, ale aj koncert C, s ktorým sa A prekrýval. Ostal mu už len jeden koncert B a toho sa teda tiež zúčastní.

   Aj tento spôsob je však chybný. Vytvorte taký zoznam koncertov (s ich začiatkami aj koncami), že opísaný postup na nich nenájde najlepšie možné riešenie. Na vašom príklade tiež ukážte, aké riešenie nájde popísaný postup a vysvetlite, prečo toto riešenie nie je optimálne.

3. (8 bodov) Sysľa už nič ďalšie nenapadlo, preto je na vás aby ste vymysleli postup, ktorým má Syseľ vyberať koncerty tak, aby ich vybral najväčší možný počet. Vo svojom riešení popíšte algoritmus – teda postupnosť krokov a pravidiel, ktoré určia, ktorých koncertov sa má Syseľ zúčastniť. Tento postup má pritom fungovať bez ohľadu na to, kedy začínajú a končia jednotlivé koncerty a koľko týchto koncertov je. Ak existuje viacero rovnako dobrých riešení, je jedno, ktoré z nich váš postup nájde.

   Dôležitou časťou vašeho riešenia musí byť aj dôkaz správnosti. Skúste popísať, prečo je vaše riešenie správne a prečo vždy nájde správnu odpoveď. Pokúste sa vyhnúť tvrdeniam "Na týchto koncertoch to funguje..." a "V takomto prípade to bude správne...". Namiesto toho vysvetlite, prečo vždy, keď váš algoritmus vyberie nejaký koncert, tak tým nič nepokazí bez ohľadu na to, ako sú umiestnené zvyšné koncerty.