Hola.
Hoy se sugirió un algoritmo alternativo para el problema de agendar todos los intervalos con la menor cantidad de recursos posible. La idea consistía en ejecutar repetidamente el algoritmo que maximiza la cantidad de intervalos atendidos con un solo recurso, cada ejecución actuando sobre el conjunto de intervalos que fueron descartados en la ejecución anterior, hasta que todos sean atendidos.
Ese algoritmo falla por ejemplo para esta instancia:
(2,3) (1,5) (6,7) (4, 8)
La primera ejecución del algoritmo ávido para maximizar la cantidad de intervalos atendidos con un solo recurso elige (2,3) y (6,7), descartando (1,5) y (4,8) que se solapan entre sí. Por lo tanto la solución generada usaría 3 recursos, a pesar de que solo se necesitan 2.
Es un lindo ejemplo para ilustrar la importancia de analizar y demostrar rigurosamente la corrección de nuestros algoritmos.
Saludos,
Álvaro