Reto de programación #1 - Fusión de Intervalos Superpuestos

Descripción del Reto

Escribe una función que fusione intervalos superpuestos en un arreglo de intervalos. Un intervalo se representa como un arreglo de dos números [inicio, fin]. Los intervalos fusionados deben estar ordenados.

Ejemplo:

Entrada: [[1,3],[2,6],[8,10],[15,18]]
Salida: [[1,6],[8,10],[15,18]]
Explicación: Los intervalos [1,3] y [2,6] se fusionan en [1,6]

Restricciones:
  1. 1 ≤ intervalos.length ≤ 10^4
  2. intervalos[i].length == 2
  3. 0 ≤ intervalos[i][0] ≤ intervalos[i][1] ≤ 10^4

Resuelve el reto

Ingresa el código para superar este reto, el botón ejecutar validará tu código con los casos de prueba.

Loading...

Pruebas unitarias

function pruebas() {
  const casos = [
    { 
      entrada: [[1,3],[2,6],[8,10],[15,18]], 
      salidaEsperada: [[1,6],[8,10],[15,18]] 
    },
    { 
      entrada: [[1,4],[4,5]], 
      salidaEsperada: [[1,5]] 
    },
    { 
      entrada: [[1,4],[2,3]], 
      salidaEsperada: [[1,4]] 
    },
    { 
      entrada: [[1,4],[0,4]], 
      salidaEsperada: [[0,4]] 
    }
  ];

  for (let i = 0; i < casos.length; i++) {
    const { entrada, salidaEsperada } = casos[i];
    const resultado = fusionarIntervalos(entrada);
    if (JSON.stringify(resultado) !== JSON.stringify(salidaEsperada)) {
      throw new Error(`Prueba ${i + 1} fallida: entrada: ${JSON.stringify(entrada)}, salida esperada: ${JSON.stringify(salidaEsperada)}, se obtuvo: ${JSON.stringify(resultado)}`);
    }
  }
  console.log("Felicitaciones, resolviste el reto, ¡Todas las pruebas pasaron!");
}
pruebas();

Solución del reto

Estrategia para fusionar intervalos:
  1. Ordenar los intervalos por su punto de inicio
  2. Recorrer los intervalos ordenados
  3. Comparar cada intervalo con el último intervalo fusionado
  4. Fusionar intervalos si hay superposición
  5. Actualizar el último intervalo fusionado
Pasos detallados:
  • Complejidad temporal: O(n log n) por el ordenamiento
  • Complejidad espacial: O(n)
  • Criterios de fusión:
    • Si no hay superposición, agregar nuevo intervalo
    • Si hay superposición, actualizar el intervalo fusionado
function fusionarIntervalos(intervalos) {
  // Caso base: si no hay intervalos o solo hay uno
  if (intervalos.length <= 1) return intervalos;
  
  // Ordenar intervalos por el punto de inicio
  intervalos.sort((a, b) => a[0] - b[0]);
  
  // Arreglo para almacenar intervalos fusionados
  const fusionados = [intervalos[0]];
  
  for (let i = 1; i < intervalos.length; i++) {
    const ultimoFusionado = fusionados[fusionados.length - 1];
    const intervaloActual = intervalos[i];
    
    // Si hay superposición, fusionar
    if (intervaloActual[0] <= ultimoFusionado[1]) {
      ultimoFusionado[1] = Math.max(ultimoFusionado[1], intervaloActual[1]);
    } else {
      // Si no hay superposición, agregar nuevo intervalo
      fusionados.push(intervaloActual);
    }
  }
  
  return fusionados;
}