Matfyz Wiki
Dnes nás hlídal Ondřej Šerý a zadal následující úlohu:
Dostaneme soubor, který má na každém řádku popis nějaké události, konkrétně čas začátku, doba trvání a jméno, například:
(...)
14:00 1:30 Písemka z MA
13:45 0:30 Něco
15:00 1:30 Přednáška
(...)
Všechny časy patří do jediného dne. Řádky jsou seřazené náhodně, jejich počet není omezený a časy se mohou překrývat. Můžeme předpokládat korektní vstup, ale časy nemusely být upravené, tedy místo "09:00 00:05" tam mohlo být třeba "9:0 0:5", a mezer mezi položkami mohlo být víc. Délka jména události omezena být mohla.
Dále byl zadaný počet místností a úkolem bylo rozvrhnout události do místností tak, aby se v rámci místnosti nepřekrývaly. Říkal, že rozvržení nemusí být nutně optimální, ať už to znamená cokoliv...
Dal nám následující pravidla:
síť byla po stažení testovacích souborů odpojena
literatura a poznámky byly povoleny (ne však opisování zdrojáků)
z C++ byla povolena syntaxe, jeho knihovny (STL) nikoliv (!)
Na řešení nám dal 3 hodiny, ale protože jsem odcházel po hodině a půl jako první, nevím, kolik na to bylo doopravdy času a jaká byla úspěšnost.
Moje dojmy:
Podle mého názoru velmi snadná úložka, pokud člověk ví, jak ji řešit algoritmicky. Já jsem znal řešení problému, jak vybrat co nejvíc nepřekrývajících se událostí, a tak jsem tímto způsobem postupně zaplnil všechny místnosti.
Jeden výběr probíhá následovně. Události se seřadí vzestupně podle času začátku. Potom se vezme první, označí se jako vybraná a přeskočí se všechny ty, které začínají dřív, než vybraná končí. Potom se vybere další a tak dále, dokud se neprojde celé pole. Seřazení lze provést pouze jednou na začátku a pak přeskakovat již zařazené události.