Tienes una sala de reuniones y un conjunto de actividades, cada una con un tiempo de inicio y fin. ¿Cuál es el mayor número de actividades no superpuestas que puedes programar?
La respuesta: siempre reserva la actividad que finaliza más temprano, luego repite. Es una de las pruebas más limpias de que una regla voraz simple puede ser óptimamente probable — y la base para la programación de intervalos en todas partes.
Cómo Funciona
- Ordena actividades por tiempo de finalización, ascendente.
- Selecciona la actividad que finaliza primero.
- Escanea el resto en orden — mantiene cualquier actividad cuyo tiempo de inicio no sea más temprano que el final de la última actividad seleccionada.
- Listo: el conjunto seleccionado es maximal.
La elección voraz es deliberada: el finalizador más temprano deja más espacio después, así que ninguna otra actividad puede bloquearlo.
Un argumento de intercambio prueba la optimalidad: toma cualquier solución óptima e intercambia su primera actividad por la de finalización más temprana. El intercambio no puede superponerse con nada que el original pudiera, y el problema restante está igual — así que la primera elección voraz es segura.
Idea Clave
La estrategia voraz funciona aquí porque la restricción es puramente sobre superposición de tiempo — una vez que eliges un finalizador, el futuro depende solo del tiempo de finalización, no de cuál actividad era. Esa sola observación colapsa todo el espacio de búsqueda. Si una actividad posterior comenzó más temprano y finalizó más tarde, solo sería peor.
Ejemplo Trabajado
El visualizador usa actividades A(1–3), B(2–5), C(4–6), D(6–8), E(5–7):
| Paso | Candidata | ¿Comienza ≥ último fin? | ¿Elegida? |
|---|---|---|---|
| 1 | A (1–3) | — (primera) | ✓ A |
| 2 | B (2–5) | 2 < 3 | ✗ |
| 3 | C (4–6) | 4 ≥ 3 | ✓ C |
| 4 | E (5–7) | 5 < 6 | ✗ |
| 5 | D (6–8) | 6 ≥ 6 | ✓ D |
Conjunto seleccionado: A, C, D — 3 actividades. Observa el visualizador recorriendo exactamente esto: cada candidata gris falla la verificación de tiempo de inicio contra el fin actual.
Casos Extremos y Trampas
- Empates en tiempo de finalización — cualquier finalizador más temprano funciona; elige cualquiera.
- Intervalos consecutivos — una actividad que finaliza en 6 y otra que comienza en 6 son compatibles (inicio ≥ fin).
- Candidatas superpuestas — B y E ambas confligen con el fin de A; el escaneo simplemente las salta.
- El ordenamiento importa — sin ordenar por tiempo de finalización, la regla voraz se rompe. Este es un preprocesamiento requerido, no una elección.
Comparación: Selección de Actividades vs Otros Problemas de Intervalos
| Problema | Regla voraz | ¿Óptimo? |
|---|---|---|
| Máx. no superpuestas | Finalización más temprana | Sí |
| Mín. salas (partición de intervalos) | Ordenar por inicio + heap | Sí |
| Mín. puntos para cubrir intervalos | Voraz por fin | Sí |
| Programación de intervalos ponderados | Finalización más temprana | No → usar DP |
Aplicaciones
- Programación de salas de reuniones — reservando una sola sala
- Asignación de aulas — empaquetando conferencias en un solo salón
- Segmentación de recursos de tiempo — programación de CPU/trabajos alrededor de fechas límite
Trayectoria de Práctica
- Ordena a mano las actividades del visualizador por tiempo de finalización y ejecuta el escaneo tú mismo.
- Explica por qué saltar B (2–5) en el paso 2 nunca puede costarte una solución.
- Construye dos actividades donde elegir el inicio más temprano (en lugar de finalización más temprana) falla.
- Extiende al problema de mín. salas y ve por qué un heap reemplaza el solo puntero.
- Prueba el argumento de intercambio para finalización-más-temprana con tus propias palabras.