Dado un conjunto de n intervalos, cada uno definido por un punto de inicio y un punto de fin ([inicio_i, fin_i]), el objetivo es seleccionar la máxima cantidad de intervalos de tal forma que ningún par de intrevalos seleccionados se solape. Se considera que los intervalos son solapados si sus puntos finales coinciden.

Por ejemplo, si tenemos los intervalos [[1, 3], [2, 4], [3, 6], [5, 7], [8, 9]], el resultado esperado es seleccionar 3 intervalos.

// Ejemplo de salida:
// { count: 3, selected: [[1, 3], [5, 7], [8, 9]] }
 

Estrategia Voraz

La estrategia voraz para resolver este problema implica los siguientes pasos:

1. Ordenar los intervalos: Ordene todos los intervalos basándose principalmente en su punto de fin en orden ascendente. Si dos intervalos comparten el mismo punto de fin, ordénelos por su punto de inicio en orden ascendente.
2. Inicializar selección: Comiance con un contador de intervalos seleccionados (count) inicializado a cero y una lista vacía para almacenar los intervalos seleccionados (selected). Mantenga un registro del punto final del último intervalo agregado a la lista (lastEnd), inicializado a un valor muy pequeño (-Infinity).
3. Iterar y seleccionar: Recorra la lista de intervalos ordenados. Para cada intervalo [inicio, fin]:
   • Si el punto de inicio de este intervalo es mayor que lastEnd, significa que este intervalo no se solapa con el último intervalo seleccionado.
   • En este caso, agregue el intervalo actual a la lista selected, incremente count, y actualice lastEnd al punto de fin del intervalo actual.
4. Resultado: Devolución del número total de intervalos seleccionados (count) y la lista de intervalos seleccionados (selected).

Implementación en JavaScript

function encontrarMaximosIntervalosNoSolapados(intervalos) {
 // Ordenar por punto final ascendente, y luego por punto de inicio ascendente si los puntos finales son iguales.
 intervalos.sort((a, b) => a[1] - b[1] || a[0] - b[0]);

 let contador = 0;
 const seleccionados = [];
 let ultimoFin = -Infinity; // Representa el punto final del último intervalo añadido

 for (const intervalo of intervalos) {
   const [inicio, fin] = intervalo;
   // Si el inicio del intervalo actual es posterior al fin del último intervalo seleccionado,
   // entonces no hay solapamiento.
   if (inicio > ultimoFin) {
     seleccionados.push(intervalo);
     contador++;
     ultimoFin = fin; // Actualizar el último punto final
   }
 }

 return {
   cantidad: contador,
   intervalosSeleccionados: seleccionados
 };
}

// Ejemplo de uso:
const listaIntervalos = [[1, 3], [2, 4], [3, 6], [5, 7], [8, 9]];
const resultado = encontrarMaximosIntervalosNoSolapados(listaIntervalos);
console.log(resultado.cantidad); // Salida esperada: 3
console.log(resultado.intervalosSeleccionados); // Salida esperada: [[1, 3], [5, 7], [8, 9]]
 

Justificación de la Estrategia Voraz

La clave de esta estrategia voraz reside en ordenar los intervalos por su punto de fin. Al priorizar los intervalos que terminan antes, nos aseguramos de maximizar el espacio disponible para seleccionar intervalos subsecuentes. Esta elección greedy es óptima porque cada decisión local (elegir el intervalo que termina más pronto) conduce a una solución global óptima.

Si intentáramos ordenar por el punto de inicio, podríamos seleccionar un intervalo que comience temprano pero que se extienda muy tarde, impidiendo la selección de múltiples intervalos más cortos que podrían haber cabido en su lugar. Al elegir el que termina antes, garantizamos que la ventana de tiempo abierta para futuras selecciones se maximiza en cada paso.