PALMA junior
Úloha o rezervovaní strojového času

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 16 / 18 = 89 %

• Úspešnosť riešenia: 3,5 / 6 = 58 %

Ak máme zistiť, či v daný deň existuje súvislý časový úsek zadanej dĺžky v ktorom nie je žiadna rezervácia, musíme si v rezerváciách spraviť poriadok. Podľa zadania máme síce zoznam rezervácií, ale rezervácie v ňom sú uvedené v nejakom chaotickom poradí.

Ideálne by bolo, ak by sme mali k dispozícii vždy dve rezervácie, ktoré idú v daný deň bezprostredne za sebou. Potom sa stačí pozrieť, či je medzi nimi dostatočný časový úsek pre novú požiadavku. Mohli by sme si rezervácie usporiadať podľa ich začiatkov. Potom stačí preskúmať každú susednú dvojicu rezervácii a zistiť, aký časový úsek je medzi koncom jednej a začiatkom druhej rezervácie. Hrubá verzia funkcie je_volno by mohla vyzerať nasledovne: 

# Python
def je_volno(cas, rezervacie):
    rezervacie.sort()
    for idx in range(len(rezervacie) - 1):
        zaciatok_volna = sum(rezervacie[idx])
        zaciatok_rezervacie = rezervacie[idx + 1][0]
        dlzka_volna = zaciatok_rezervacie - zaciatok_volna
        if dlzka_volna >= cas:
            return True
    return False

Toto riešenie má niekoľko problematických bodov:

1. Ak zoznam rezervacia vo funkcii je_volno usporiadame, táto zmena sa prejaví aj v hlavnom programe. Toto je nežiadúce. Tento problém odstránime jednoducho - vytvoríme si kópiu zoznamu rezervacia a pracovať budeme s ňou.

2. Voľný úsek hľadáme len medzi dvoma rezerváciami. V skutočnosti môže byť voľný úsek pred prvou, ale aj za poslednou rezerváciou. Tento problém môžeme vyriešiť tak, že do zoznamu vložíme dve umelé rezervácie.

   • Prvú rezerváciu vložíme na začiatok tak, aby skončila v sekunde -1. Ďalšia rezervácia teda bude môcť začať v sekunde 0.

   • Druhú rezerváciu vložíme na koniec tak, aby začínala v sekunde 86400. Predchádzajúca teda môže končiť v sekunde 86399, čo je posledná sekunda dňa.

Keďže obidve vložené rezervácie sú umiestnené mimo dňa, nenastane žiaden konflikt s niektorou s existujúcich rezervácií.

Výsledná verzia funkcie je_volno môže vyzerať nasledovne:

# Python
def je_volno(cas, rezervacie):
    rezervacie_tmp = rezervacie.copy()
    rezervacie_tmp.sort()
    rezervacie_tmp.insert(0, [-1, 1])
    rezervacie_tmp.append([60 * 60 * 24, 0])
    for idx in range(len(rezervacie_tmp) - 1):
        zaciatok_volna = sum(rezervacie_tmp[idx])
        zaciatok_rezervacie = rezervacie_tmp[idx + 1][0]
        dlzka_volna = zaciatok_rezervacie - zaciatok_volna
        if dlzka_volna >= cas:
            return True
    return False

Niekomu by mohlo napadnúť, že usporiadať zoznam je neefektívne. Môžeme predsa zo zoznamu vyberať rezervácie postupne od najskoršej. Dvojicu rezervácii s dostatočným časovým úsekom môžeme nájsť už niekde na začiatku. To je síce pravda, ale spoliehať sa na to nemôžeme. Nastať môže aj opačný prípad. Voľný súvislý časový úsek danej dĺžky neexistuje. Postupné vyberanie najskoršej rezervácie zo zoznamu by bolo omnoho náročnejšie ako úvodné usporiadanie zoznamu. 

Vaše zaujímavé riešenia a najčastejšie chyby

Úlohu riešilo 16 tímov. Správne riešenie malo 5 tímov. Medzi časté problémy patrilo správne pochopenie zadania:

• požiadavka vedca je len dĺžka rezervácie a nie čas, kedy chce rezerváciu zaradiť,
• rezervácie v zozname nemusia byť nutne usporiadané.

 Niektorí neuvažovali zaradenie požiadavky na začiatok alebo na koniec zoznamu, ale len medzi dve už existujúce rezervácie..