Дуусах хугацаа ба үргэлжлэх хугацаа өгөгдсөн үеийн ажлын оновчтой хуваарь¶

Бидэнд ажлуудын багц байгаа бөгөөд ажил бүрийн дуусах хугацаа ба үргэлжлэх хугацааг нь мэддэг гэж үзье. Ажлын гүйцэтгэлийг дуусахаас нь өмнө тасалж болохгүй. Хамгийн олон тооны ажлыг гүйцэтгэх ийм хуваарь зохиох шаардлагатай.

Бодох нь¶

Бодох алгоритм нь greedy юм. Бүх ажлыг дуусах хугацаагаар нь эрэмбэлж, буурах дарааллаар харцгаая. Мөн $q$ дараалал үүсгэе; бид түүн рүү ажлуудыг аажмаар хийж, ажиллах хугацаа хамгийн багатайг нь гаргаж авна (жишээ нь бид set эсвэл priority_queue ашиглаж болно). Эхэндээ $q$ хоосон байна.

Бид $i$ дугаар ажлыг харж байна гэж үзье. Юуны өмнө түүнийг $q$ рүү хийе. $i$ дугаар ажлын дуусах хугацаа ба $i-1$ дугаар ажлын дуусах хугацааны хоорондох хугацааны интервалыг авч үзье. Энэ бол ямар нэг $T$ урттай хэрчим юм. Бид $q$-аас ажлуудыг гаргаж авч (үлдсэн үргэлжлэх хугацааны өсөх дарааллаар) $T$ хэрчим бүхэлдээ дүүргэгдэх хүртэл гүйцэтгэнэ. Чухал: хэрэв ямар нэг агшинд гаргаж авсан ажлыг зөвхөн хэсэгчлэн буюу $T$ хэрчим дүүргэгдэх хүртэл гүйцэтгэж болох бол бид энэ ажлыг боломжтой хэрээр буюу $T$ хугацааны туршид хэсэгчлэн гүйцэтгээд, ажлын үлдсэн хэсгийг $q$ руу буцаан хийнэ.

Алгоритм дуусахад бид оновчтой шийдлийг (эсвэл ядаж хэд хэдэн шийдлийн нэгийг) сонгоно. Алгоритмын ажиллах хугацаа нь $O(n \log n)$.

Implementation¶

The following function takes a vector of jobs (consisting of a deadline, a duration, and the job's index) and computes a vector containing all indices of the used jobs in the optimal schedule. Notice that you still need to sort these jobs by their deadline, if you want to write down the plan explicitly.

struct Job {
    int deadline, duration, idx;

    bool operator<(Job o) const {
        return deadline < o.deadline;
    }
};

vector<int> compute_schedule(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end());

    set<pair<int,int>> s;
    vector<int> schedule;
    for (int i = jobs.size()-1; i >= 0; i--) {
        int t = jobs[i].deadline - (i ? jobs[i-1].deadline : 0);
        s.insert(make_pair(jobs[i].duration, jobs[i].idx));
        while (t && !s.empty()) {
            auto it = s.begin();
            if (it->first <= t) {
                t -= it->first;
                schedule.push_back(it->second);
            } else {
                s.insert(make_pair(it->first - t, it->second));
                t = 0;
            }
            s.erase(it);
        }
    }
    return schedule;
}