Greedy y argumento de intercambio

Tema: Greedy · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 23 de la Ruta de Aprendizaje.

Qué hace

Toma en cada paso la decisión localmente mejor y no mira atrás; el argumento de intercambio es la herramienta con que se demuestra que esa decisión no cierra la puerta al óptimo.

Complejidad: O(n log n) casi siempre: el costo es el sort que impone el criterio, y la pasada posterior es O(n).

Cuándo usarlo

Cuando sospechas que un criterio simple de orden resuelve el problema. Antes de programarlo, intenta el intercambio: si te sale, tienes solución corta y segura; si no te sale, desconfía y mira hacia Programación Dinámica.

Implementación recomendada (C++)

// Patrón 1 — selección de actividades: máximo de intervalos que no se topan.
// El intercambio demuestra que el criterio correcto es el FIN, no el inicio
// ni la duración.
int max_actividades(vector<pair<int,int>> v) {   // v = {fin, inicio}; por valor: se ordena una copia
    sort(v.begin(), v.end());                    // por fin creciente
    int tomadas = 0;
    int libre = INT_MIN;                         // aún no termina nada
    for (auto [fin, inicio] : v)
        if (inicio >= libre) { tomadas++; libre = fin; }
    return tomadas;
}
 
// Patrón 2 — minimizar la suma de tiempos de espera (shortest job first).
// El intercambio se hace sobre dos tareas VECINAS: si la larga va antes que la
// corta, todas las de atrás esperan de más; darlas vuelta nunca empeora.
long long espera_total(vector<long long> duracion) {
    sort(duracion.begin(), duracion.end());      // la más corta primero
    long long reloj = 0, total = 0;
    for (long long d : duracion) {
        reloj += d;                              // cuándo termina esta
        total += reloj;                          // ...es lo que esperó
    }
    return total;
}

⚠️ Notas

El molde de la demostración: toma una solución óptima cualquiera, encuentra la primera decisión donde difiere del greedy, intercambia esa decisión por la del greedy y muestra que la solución sigue siendo válida y no empeora. Entonces existe una óptima que empieza como el greedy; repitiendo el argumento, el greedy entero es óptimo. ⚠️ El error caro no es programar mal el greedy: es elegir mal el criterio de orden. Ordenar actividades por duración o por inicio parece igual de razonable y da respuestas peores — el intercambio es lo único que distingue. Si no logras hacer el intercambio, no asumas que igual funciona: móntale un stress test contra fuerza bruta (módulo 24) con n ≤ 8. En dos minutos tienes el contraejemplo o la confianza. Y ojo con el empate inicio >= libre: si el enunciado no permite que una actividad empiece justo cuando termina la anterior, es >.

🔗 Relacionados