Cronograma ideal de trabalhos com deadlines e durações

Suponhamos que tenhamos um conjunto de trabalhos e estamos cientes do prazo/deadline de cada trabalho e de sua duração. A execução de um trabalho não pode ser interrompida antes do final. É necessário criar um cronograma para realizar o maior número de tarefas.

Resolução

O algoritmo da solução é greedy. Vamos ordenar todos os trabalhos de acordo com seus prazos e examiná-los em ordem decrescente. Além disso, vamos criar uma queue $q$, na qual gradualmente colocaremos os trabalhos e extrairemos o trabalho com o menor tempo de execução (por exemplo, podemos usar set ou priority_queue). Inicialmente, $q$ está vazia.

Suponha que estamos analisando o $i$-ésimo trabalho. Primeiro de tudo, vamos colocar em $q$. Vamos considerar o período entre a deadline do $i$-ésimo trabalho e a deadline do $i-1$-ésimo trabalho. Esse é o segmento de algum comprimento $T$. Extrairemos os trabalhos de $q$ (na ordem crescente de duração) e os executaremos até que todo o segmento $T$ seja preenchido. Importante: se a qualquer momento o trabalho extraído puder ser executado apenas parcialmente até que o segmento $T$ for preenchido, então, executamos esse trabalho parcialmente o máximo possível, ou seja, durante o período de $T$, e colocamos a parte restante de um trabalho de volta em $q$.

Na conclusão do algoritmo, escolheremos a solução ideal (ou, pelo menos, uma das várias soluções). O tempo de execução do algoritmo é $O(n \log n)$.

Implementação

A função a seguir pega um vetor de trabalhos (que consiste em uma deadline, uma duração, e o índice do trabalho) e calcula um vetor que contém todos os índices dos trabalhos usados ​​na programação ideal. Observe que ainda é necessário ordenar esses trabalhos pelas deadlines, se for necessário anotar esse plano explicitamente.

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