Plan óptimo dados deadlines y duraciones

Supongamos que tenemos un conjunto de trabajos, y conocemos el deadline y la duración de cada trabajo. La ejecución de un trabajo no se puede interrumpir antes de su final. Se pide crear un plan tal que se complete el mayor número de trabajos.

Resolución

El algoritmo de resolución es voraz. Ordenemos todos los trabajos por sus deadlines y mirémoslos en orden descendente. También, creemos una cola $q$, en la que iremos poniendo gradualmente los trabajos y extraeremos el de menor tiempo de ejecución (por ejemplo, podemos usar set o priority_queue). Inicialmente, $q$ está vacía.

Supongamos que estamos mirando el $i$-ésimo trabajo. Ante todo, pongámoslo en $q$. Consideremos el período de tiempo entre el deadline del $i$-ésimo trabajo y el deadline del $(i-1)$-ésimo trabajo. Ese es el segmento de alguna longitud $T$. Extraeremos trabajos de $q$ (en orden creciente de su duración restante) y los ejecutaremos hasta que todo el segmento $T$ esté lleno. Importante: si en cualquier momento el trabajo extraído solo se puede ejecutar parcialmente hasta que el segmento $T$ se llene, entonces ejecutamos este trabajo parcialmente justo hasta donde sea posible, es decir, durante el tiempo $T$, y ponemos la parte restante de un trabajo de vuelta en $q$.

Al completar el algoritmo elegiremos la solución óptima (o, al menos, una de varias soluciones). El tiempo de ejecución del algoritmo es $O(n \log n)$.

Implementación

La siguiente función toma un vector de trabajos (consistente en un deadline, una duración, y el índice del trabajo) y computa un vector que contiene todos los índices de los trabajos usados en el plan óptimo. Nótese que todavía hay que ordenar estos trabajos por su deadline, si se quiere escribir el plan explícitamente.

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