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; }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. ∎
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.
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:
| Orden | Termina la primera | Termina la segunda | Suma de ambas |
|---|---|---|---|
| a, b | T + a | T + a + b | 2T + 2a + b |
| b, a | T + b | T + b + a | 2T + 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.
Idea para comprobar tu solución
Ordena por fin y elige [0,3] y [3,6]. El intercambio reemplaza la primera película de una óptima, conservando cantidad y espacio posterior.
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.
Una pista, si la necesitas
Prueba tu criterio en un caso donde la actividad que empieza primero ocupa mucho tiempo.
Contrastar el razonamiento
Por fin creciente se pueden elegir
(1,2),(2,3),(3,5). La alternativa que empieza más temprano,(0,4), solo deja lugar a una actividad más. Justifica el criterio por intercambio, no solo por este ejemplo.
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):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Cola | Regional 2025 | scheduling por intercambio |
| 2 | Pájaros furiosos | Regional 2022 | emparejar de mayor a menor, justificando |
| 3 | ⭐ Poleras | Regional 2023 | greedy con ventana y argumento de intercambio |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Ferris Wheel (CSES 1090) | ★★★ (—) | emparejar extremos (sort + dos punteros) |
| 2 | Movie Festival (CSES 1629) | ★★★ (—) | el clásico de la lección |
| 3 | Stick 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?
Si el diagrama no cabe, deslízalo horizontalmente.
Ver razonamiento
El greedy elige A y luego B: obtiene dos películas y 2 puntos. Es óptimo para la cantidad, pero elegir solo C da 10 puntos. En la demostración original, reemplazar la primera película de una solución por otra que termina antes conserva la cantidad y deja espacio para el resto. Con recompensas distintas, el reemplazo puede perder puntaje: justo esa parte del argumento deja de funcionar. La corrección depende del objetivo que se demuestra, no solo de que las entradas sean intervalos.
← 22 - Programación dinámica II · Ruta de Aprendizaje · 24 - Entrenar con problemas IOI →