23 · Greedy demostrable

Estructuras y algoritmos avanzados · Ruta de Aprendizaje

Antes de empezar. Ordenar y leer pares: 05 - Ordenamiento y 06 - Conjuntos, mapas y pares. Para la ampliación que compara soluciones exhaustivas, 13 - Backtracking.

Lectura para Regional

La selección de actividades y su argumento de intercambio forman una introducción completa. No necesitas backtracking ni programación dinámica para esas secciones; puedes dejar «Otro intercambio» para después.

🎯 Objetivos

Al terminar este módulo sabes:

  • Diseñar estrategias voraces… y justificar por qué funcionan.
  • Usar el argumento de intercambio, tu herramienta de demostración estrella.
  • Detectar los greedy falsos antes de que te cuesten un WA.

📖 La lección

Greedy: decidir lo mejor ahora, para siempre

Una estrategia voraz toma en cada paso la decisión localmente mejor y no mira atrás. Para aceptarla, hay que demostrar que sus decisiones permiten alcanzar una solución óptima. El problema: a veces no funciona. Para pagar 6 con monedas de valores {1, 3, 4}, tomar la mayor posible da 4+1+1 (tres monedas), pero 3+3 usa dos. La programación dinámica estudiará después una forma de comparar alternativas. La diferencia entre un greedy y una corazonada es la demostración.

El clásico resuelto bien: selección de actividades

Queremos ver la mayor cantidad de películas completas sin superponer horarios. Se permite comenzar una justo cuando termina otra.

Compara estas cuatro películas: A=[0,3], B=[3,6], C=[0,6], D=[2,4]. Elegir la de inicio más temprano puede tomar C en un empate y quedarse con una. Elegir la más corta toma D e impide A y B: también una. Por término, elige A y luego B: dos. Este ejemplo refuta las primeras reglas, pero todavía no demuestra la tercera para todas las entradas.

La regla candidata es ordenar por hora de término y tomar cada película compatible con las elegidas. La figura sigue las mismas cuatro películas; el código guarda (fin,inicio) para que el orden de los pares aplique esa regla:

El ejemplo supone horas de inicio no negativas, cada fin posterior a su inicio y que se permite empezar justo cuando termina otra película. Cada par guarda (fin, inicio). auto [fin, inicio] nombra sus dos componentes, como leer .first y .second. libre indica desde cuándo podemos comenzar la siguiente película.

// supone: vector<pair<int,int>> pelis;  // (fin, inicio) de cada película
sort(pelis.begin(), pelis.end()); // pares (fin, inicio): el fin primero
int vistas = 0, libre = 0;
for (auto [fin, inicio] : pelis)
    if (inicio >= libre) { vistas++; libre = fin; }
0123456AsíDnoCnoBsíPor fin: A, D, C, B → elegimos A y BEn el empate de fin, (fin,inicio) ordena C antes que B.

Si el diagrama no cabe, deslízalo horizontalmente.

El argumento de intercambio

Supón una solución óptima que no toma la película que termina primero (llámala P). Sea X la primera película de esa solución, como en el dibujo. P termina como máximo cuando termina X, así que cambiar X por P nunca estorba a las películas posteriores: la solución sigue siendo válida y del mismo tamaño. Luego existe una óptima que empieza como el greedy; repitiendo el argumento, el greedy completo es óptimo. ∎

una óptima cualquiera, que no toma PXYZPP termina antes que X (es la que termina primero de todas)cambia X por P: sigue válida, mismo tamañoPYZP no puede chocar con Y: termina antes que X, y X no chocaba con Yluego existe una óptima que empieza como el greedy; repitiendo el argumento, el greedy es óptimo ∎

Si el diagrama no cabe, deslízalo horizontalmente.

Ese molde — “toma una óptima, intercambia su decisión por la del greedy, muestra que no empeora” — demuestra la mayoría de los greedy correctos. Y si no logras hacer el intercambio, todavía falta una justificación: puede necesitar otra demostración o ser falso. Un contraejemplo sí lo refuta; la dificultad para demostrarlo no basta para descartarlo. El molde de la demostración y los dos patrones clásicos están en Greedy y argumento de intercambio; más del tema, en Greedy.

Otro intercambio: ordenar tareas

Aquí todas las tareas deben realizarse y elegimos su orden. Hay una sola persona o máquina, las tareas están disponibles desde el tiempo 0, no se interrumpen y todas pesan lo mismo en el objetivo. Queremos minimizar la suma de sus tiempos de finalización: para cada tarea anotamos cuándo termina y sumamos esos instantes. No es la suma de duraciones, que no cambia.

Por ejemplo, A dura 5 y B dura 2. Si hacemos A primero, termina en 5 y B en 7: suman 12. Si hacemos B primero, termina en 2 y A en 7: suman 9. El trabajo completo sigue terminando en 7, pero la tarea corta espera menos.

A dura 5; B dura 2. Ambas están listas en 0.0A5B7Finalizan en 5 y 7: suma 120B2A7Finalizan en 2 y 7: suma 9La tarea corta termina antes; el final total no cambia.

Si el diagrama no cabe, deslízalo horizontalmente.

El ejemplo sugiere ordenar por duración creciente. Para justificarlo en cualquier lista, tomemos dos tareas consecutivas, con duraciones a > b, que empiezan después de un tiempo T:

OrdenTermina la primeraTermina la segundaSuma de ambas
a, bT + aT + a + b2T + 2a + b
b, aT + bT + b + a2T + 2b + a

La suma disminuye en a − b. Las tareas anteriores no cambian y las posteriores empiezan a la misma hora: el bloque sigue durando a+b. Por tanto, intercambiar ese par mejora el objetivo sin perjudicar el resto. Si aún hay una tarea larga justo antes de una corta, repetimos. Al eliminar esas inversiones obtenemos duraciones de menor a mayor; ningún otro orden tiene una suma menor. Los empates de duración no afectan el resultado.

El objetivo importa: esta prueba minimiza la suma de tiempos de finalización, no demuestra selección de películas ni emparejamiento. Cada aplicación de la práctica necesita su propio argumento.

Detector de greedy falsos

Antes de enviar: (1) ¿el intercambio realmente funciona o solo suena bien?, (2) prueba cientos de casos chicos contra una fuerza bruta del módulo 13, automatizado — es el stress testing que arma el módulo 24, y son cinco minutos que ahorran horas. En competencia, un WA de greedy falso es de los errores más caros: parece correcto y no sabes dónde mirar.

🏋️ Práctica

Práctica directa: Elegir y justificar

Películas [0,3],[3,6],[0,6],[2,4]; se permite empezar al terminar otra. Imprime la cantidad máxima: 2.

Variación: Cambiar los horarios

Selecciona la mayor cantidad de actividades compatibles entre (inicio,fin) = {(0,4),(1,2),(2,3),(3,5),(4,6)}. Se permite empezar justo al terminar otra. La respuesta es 3.

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Problemas OCI reales, en español (cada nota trae el link a su mirror):

#ProblemaFaseQué practica
1ColaRegional 2025scheduling por intercambio
2Pájaros furiososRegional 2022emparejar de mayor a menor, justificando
3⭐ PolerasRegional 2023greedy con ventana y argumento de intercambio

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Ferris Wheel (CSES 1090)★★★ (—)emparejar extremos (sort + dos punteros)
2Movie Festival (CSES 1629)★★★ (—)el clásico de la lección
3Stick Lengths (CSES 1074)★★★ (—)por qué la mediana (¡demuéstralo!)
4⭐ Tasks and Deadlines (CSES 1630)★★★★ (—)intercambio puro: ¿en qué orden conviene?

Para pensar: cambiar el objetivo rompe el intercambio

Hay tres películas: A va de 0 a 2 y vale 1 punto; B va de 2 a 4 y vale 1; C va de 0 a 4 y vale 10. Puedes empezar otra justo cuando termina una. ¿Elegir siempre la que termina antes maximiza la cantidad? ¿Y el puntaje?

Mismo tiempo, distintas recompensas01234A · 1 puntoB · 1 puntoC · 10 puntosEl final de A coincide con el inicio de B.

Si el diagrama no cabe, deslízalo horizontalmente.


← 22 - Programación dinámica II · Ruta de Aprendizaje · 24 - Entrenar con problemas IOI →