마감 기한과 소요 시간이 주어진 작업들의 최적 스케줄¶

작업들의 집합이 있고, 각 작업의 마감 기한과 소요 시간을 알고 있다고 가정합시다. 작업은 한 번 실행되면 끝날 때까지 중단할 수 없습니다. 가능한 한 많은 작업을 완료할 수 있는 스케줄을 만들어야 합니다.

풀이¶

풀이 알고리즘은 그리디입니다. 모든 작업을 마감 기한 기준으로 정렬한 다음 내림차순으로 살펴봅시다. 또한 큐 $q$를 만들어, 여기에 작업을 차례로 넣고 실행 시간이 가장 짧은 작업을 꺼내도록 합시다(예를 들어 set이나 priority_queue를 사용할 수 있습니다). 처음에 $q$는 비어 있습니다.

$i$번째 작업을 살펴보고 있다고 가정합시다. 먼저 이 작업을 $q$에 넣습니다. $i$번째 작업의 마감 기한과 $i-1$번째 작업의 마감 기한 사이의 시간 구간을 생각해 봅시다. 이는 어떤 길이 $T$인 구간입니다. 구간 $T$ 전체가 채워질 때까지 $q$에서 작업을 (남은 소요 시간의 오름차순으로) 꺼내어 실행합니다. 중요: 어느 시점에서든 꺼낸 작업을 구간 $T$가 채워질 때까지 일부만 실행할 수 있다면, 이 작업을 가능한 만큼만, 즉 $T$ 시간 동안 부분적으로 실행하고 작업의 남은 부분은 다시 $q$에 넣습니다.

알고리즘이 끝나면 최적해(또는 적어도 여러 해 중 하나)를 선택하게 됩니다. 알고리즘의 실행 시간은 $O(n \log n)$입니다.

구현¶

다음 함수는 작업들의 벡터(마감 기한, 소요 시간, 작업 인덱스로 구성됨)를 받아, 최적 스케줄에 사용된 모든 작업의 인덱스를 담은 벡터를 계산합니다. 계획을 명시적으로 적으려면 이 작업들을 여전히 마감 기한 기준으로 정렬해야 한다는 점에 유의하십시오.

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;
}