6. Odďaľovanie roboty vzorové riešenie

2 0
10 5
7 1

4

3 1
10 3
8 2
6 2

5

2 0
10 10
2 2

Neda sa to stihnut.

Najprv si ukážeme, ako sa dal riešiť ľahší problém, kedy chceme stihnúť všetky úlohy. Potom si ukážeme, ako sa dal riešiť zložitejší problém, kedy môžeme nejaké úlohy vynechať.

Ľahšia úloha – riešenie jednoduchou myšlienkou

Intuitívne by sa mohlo zdať, že keď chceme maximalizovať čas flákania sa na začiatku, tak chceme riešiť úlohy čo najneskôr, teda čo najbližšie k ich deadlajnu. Ináč povedané, ak má úloha \(i\) deadline \(d_i\) a jej splnenie trvá \(t_i\) času, tak by sme ju ideálne chceli začať plniť v čase \(d_i - t_i\).

Bohužiaľ toto sa nedá vždy urobiť. Napríklad, ak máme úlohu, ktorú treba splniť do času \(6\) a jej plnenie trvá \(3\) jednotky času a úlohu, ktorej deadline je \(5\) a máme na ňu tiež \(3\) jednotky času. Podľa vyššie spomenutej stratégie chceme prvú úlohu začať v čase \(3\) a skončiť v čase \(6\) a druhú úlohu chceme začať v čase \(2\) a skončiť v čase \(5\). To je ale problém, lebo nevieme robiť na dvoch úlohách naraz.

Nevieme teda obe úlohy splniť tesne pred deadlajnom. Máme na výber z dvoch možností: buď splníme tesne pred deadlajnom prvú, alebo druhú úlohu. Náš cieľ je flákať sa čo najdlhšie na začiatku, takže bude lepšie, ak splníme tesne pred deadlajnom úlohu, ktorá má neskorší deadline. Čiže druhú úlohu začneme plniť v čase \(0\), skončíme v čase \(3\), a potom robíme prvú úlohu, ktorú dokončíme v čase \(6\) – tesne pred deadlajnom.

Ak si to zosumarizujeme, tak sme vlastne urobili dve pozorovania. Prvé pozorovanie je, že chceme riešiť úlohu čo najbližšie k jej deadlajnu. Druhé pozorovanie je, že občas sa to nedá, keď sa intervaly plnenia úloh prekrývajú. Tento prípad vieme riešiť tak, že úlohu, ktorej deadline je neskoršie, budeme končiť presne v čase deadlajnu a intervaly pre ostatné úlohy trocha poposúvame doľava (na časovej osi).

Ľahšia úloha – algoritmus

Táto stratégia sa dá zovšeobecniť do algoritmu. Najprv utriedime všetky úlohy podľa deadlajnu zostupne, a potom prechádzame cez takto utriedené úlohy. Počas tohto prechodu si udržiavame čas \(x\) – kedy sme začali plniť poslednú úlohu v našom poradí. Zistime, kedy začneme plniť \(i\)-tu úlohu v našom poradí:

• Ak \(d_i \geq x\), úlohu nemôžeme začať plniť tesne pred deadlajnom, lebo v čase \(d_i\) už riešime jednu z nasledujúcich úloh. Začneme preto túto úlohu plniť už v čase \(x - t_i\).
• Inak začneme úlohu plniť v čase \(d_i - t_i\) (tesne pred deadlajnom).

Potom nastavíme \(x\) na novú hodnotu a pokračujeme ďalšou úlohou. To, čo nám na záver zostane v premennej \(x\) je náš výsledok – čas, kedy sme začali plniť prvú úlohu.

Časová zložitosť tohto riešenia je \(O(n \log n)\), kde \(n\) je počet úloh. Triedenie je najpomalšia operácia. Zvyšok je iba prechod poľom.

Pamäťová zložitosť je \(O(n)\), lebo si musíme pamätať všetky úlohy.

Ľahšia úloha – dôkaz správnosti

Pri takýchto greedy algoritmoch je dôležité si zdôvodniť, prečo náš algoritmus skutočne nájde optimálne riešenie.

Zoberme si ľubovoľné poradie úloh, ktoré dáva najlepšie riešenie, teda nám dovolí flákať sa na začiatku najdlhšie a porovnajme toto riešenie s riešením, ktoré vytvorí náš algoritmus. Chceme ukázať, že naše riešenie nám dovolí sa flákať na začiatku aspoň tak dlho ako optimálne riešenie.

Zoberme si z optimálnej postupnosti úlohu \(i\), ktorá má deadline najneskôr a presuňme ju na koniec postupnosti úloh. Takto dosiahneme to, že túto úlohu budeme končiť presne v čase jej deadlajnu. Ak sme v optimálnom poradí v čase od \(d_i - t_i\) riešili inú úlohu, musíme posunúť interval jej riešenia doľava (na časovej osi) a takisto aj intervaly ostatných predošlých úloh.

Dôležité je všimnúť si, že intervaly neposunieme viac doľava než bol pôvodný začiatok intervalu riešenia úlohy \(i\). Tým, že sme presunuli úlohu \(i\) na koniec sme totiž využili časový interval medzi deadlajnom predposlednej úlohy a deadlajnom poslednej úlohy, \(i\). Vďaka tomu nemusíme posúvať intervaly, pre úlohy ktoré sme v optimálnom riešení začali riešiť pred \(i\), a teda touto operáciou určite nezhoršíme optimálne riešenie.

Teraz si zoberme úlohu s druhým najneskorším deadlajnom a presuňme ju na predposlednú pozíciu. Znova platia podobné argumenty, že si týmto nezhoršíme naše riešenie. Tento postup budeme opakovať pre všetky intervaly. Takto dostaneme poradie úloh, v akom by ich vykonával náš algoritmus, čiže vlastne vieme prerobiť ľubovoľné optimálne riešenie na naše riešenie a nezhoršiť ho. To znamená, že naše riešenie musí byť jedno z optimálnych.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int N, K;
    scanf(" %d %d", &N, &K);

    vector<pair<int, int>> ulohy(N);
    for (int i = 0; i < N; ++i) {
        scanf(" %d %d", &ulohy[i].first, &ulohy[i].second);
    }

    // utried ulohy zostupne podla deadlinu.
    sort(ulohy.begin(), ulohy.end(), greater<pair<int, int>>());

    int zaciatok_poslednej_ulohy = INT_MAX;
    for (const pair<int, int>& uloha : ulohy) {
        int deadline = uloha.first;
        int trvanie = uloha.second;
        if (deadline > zaciatok_poslednej_ulohy) {
            if (zaciatok_poslednej_ulohy - trvanie < 0) {
                printf("Neda sa to stihnut.\n");
                return 0;
            }
            zaciatok_poslednej_ulohy -= trvanie;
        } else {
            zaciatok_poslednej_ulohy = deadline - trvanie;
        }
    }

    printf("%d\n", zaciatok_poslednej_ulohy);
    return 0;
}

Pôvodná úloha

Teraz sa pozrime na úlohu pre \(k>0\). V tomto prípade už nejde riešiť túto úlohu greedy spôsobom. Ak by sme napríklad použili stratégiu, ktorou sme riešili prípad \(k=0\), tak sa nám nie vždy musí oplatiť zobrať úlohu s najneskorším deadlajnom. Ak práca na poslednej úlohe trvá veľmi dlho, oplatí sa nám ju vynechať a namiesto nej splniť ostatné úlohy.

Greedy algoritmy sa vyznačujú tým, že sú veľmi rýchle. Keď si poriadne pozrieme obmedzenia v zadaní úlohy, tak zistíme, že postačí aj pomalšie riešenie. Na riešenie použijeme techniku zvanú dynamické programovanie. Pri dynamickom programovaní si najprv jednoducho definujeme problém, a potom sa pomocou menších podproblémov snažíme vyskladať ten väčší. Najprv riešime malé problémy a z nich skladáme riešenia pre väčšie a väčšie problémy.

Náš problém je definovaný postupnosťou úloh a počtom úloh, ktoré chceme vynechať. Ako podproblém si teda definujeme, že chceme zistiť, ako najdlhšie sa môžeme flákať, ak chceme z prvých \(i\) úloh vynechať najviac \(j\). Pričom stále chceme spracúvať úlohy v takom istom poradí, ako sme to robili v riešení pre ľahší problém – od najneskoršieho deadlajnu po najskorší. Riešenie pre podproblémy si budeme ukladať do tabuľky \(P\), aby sme ich nemuseli rátať viackrát. Pričom na \(P[i][j]\) je uložené číslo, ako najdlhšie sa môžeme flákať ak chceme vynechať najviac \(j\) úloh z prvých \(i\).

Začnime triviálnym prípadom, keď chceme z prvých nula úloh nestihnúť najviac \(j\) úloh. V takom prípade sa môžeme nekonečne dlho flákať, takže do prvého riadku dáme samé nekonečná.

Zoberme si prípad, keď \(i>0\). V takom prípade máme dve možnosti. V optimálnom riešení \(P[i][j]\) sa nachádza alebo nenachádza úloha \(i\):

• Ak sa v riešení nenachádza úloha \(i\), tak je toto riešenie zhodné s riešením pre \(P[i-1][j-1]\). Čiže v takom prípade sa môžeme flákať \(P[i-1][j-1]\) času.

• Ak sa v tomto riešení nachádza úloha \(i\), tak odobratím \(i\) dostaneme optimálne riešenie pre podúlohu \(P[i-1][j]\). Toto sa dá jednoducho dokázať sporom. Ak by to nebolo optimálne riešenie, tak potom odobratím úlohy \(i\) dostaneme lepšie riešenie pre podproblém \(P[i-1][j]\), čo je spor.

  Otázkou ešte je, kedy začneme (a skončíme) plniť úlohu \(i\). Buď ju skončíme skončíme v čase deadlajnu, alebo v čase, keď začneme prvú úlohu z riešenia \(P[i-1][j]\). Ak je deadline pred začiatkom prvej úlohy v riešení pre \(P[i-1][j]\), tak musíme úlohu \(i\) začať v čase \(d_i - t_i\). Ak už počas \(d_i\) riešime jednu z neskorších úloh, začneme \(i\) riešiť v čase \(P[i-1][j] - t_i\) a skončíme v čase \(P[i-1][j]\).

Z oboch týchto možností si vyberieme tú, ktorá nám dovolí sa najviac flákať. \[P[i][j] = \max(P[i-1][j-1],\min(d_i-t_i,P[i-1][j] - t_i))\]

Túto tabuľku si počítame po riadkoch a finálny výsledok sa nachádza na políčku \(P[N][K]\) – ako najdlhšie sa môžeme flákať ak chceme vynechať najviac \(K\) úloh z prvých \(N\).

Časová zložitosť tohto riešenia je \(O(nk)\) a pamäťová tiež. Môžeme si všimnúť, že na vypočítanie nového riadku v tabuľke potrebujeme iba predchádzajúci riadok, takže vieme pamäťovú zložitosť vylepšiť na \(O(k)\) tým, že si budeme pamätať iba posledné dva riadky tabuľky.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int N, K;
    scanf(" %d %d", &N, &K);

    vector<pair<int, int>> ulohy(N);
    for (int i = 0; i < N; ++i) {
        scanf(" %d %d", &ulohy[i].first, &ulohy[i].second);
    }

    // utried ulohy zostupne podla deadlinu.
    sort(ulohy.begin(), ulohy.end(), greater<pair<int, int>>());

    vector<vector<int>> dp(N + 1, vector<int>(K + 1));
    fill(dp[0].begin(), dp[0].end(), INT_MAX);
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= K; ++j) {
            int deadline = ulohy[i - 1].first;
            int trvanie = ulohy[i - 1].second;
            // zaporne cislo znamena, ze sa to neda.
            int urob_ulohu = min(deadline - trvanie, dp[i - 1][j] - trvanie);
            int vynechaj_ulohu = j > 0 ? dp[i - 1][j - 1] : -1;
            dp[i][j] = max(vynechaj_ulohu, urob_ulohu);
        }
    }

    if (dp[N][K] < 0)
        printf("Neda sa to stihnut.\n");
    else
        printf("%d\n", dp[N][K]);
    return 0;
}