Estoy intentando resolver el problema de la combinación de intervalos superpuestos y tengo la solución de trabajo a continuación. Sin embargo, hay una parte de la lógica que tengo problemas para entender. Es decir, la parte en la que currentInterval[1] se actualiza con el máximo entre currentInterval[1] y nextInterval[1]. Este fragmento de código también actualiza la última matriz en la matriz mergedIntervals y no entiendo completamente cómo sucede esto, ya que no veo cómo el intervalo actual está vinculado con la última matriz en mergedIntervals. ¿Podría alguien explicar cómo se actualizan mergedIntervals cuando configuramos currentInterval[1]?
const array = [ [1, 2], [4, 7], [9, 10], [3, 5], [6, 8], ]; function mergeOverlappingIntervals(array) { let sortedIntervals = array.sort(function (a, b) { return a[0] - b[0]; }); let mergedIntervals = []; let currentInterval = sortedIntervals[0]; mergedIntervals.push(currentInterval); for (let nextInterval of sortedIntervals) { if (currentInterval[1] >= nextInterval[0]) { currentInterval[1] = Math.max( currentInterval[1], nextInterval[1], ); } else { currentInterval = nextInterval; mergedIntervals.push(nextInterval); } } return mergedIntervals; } const result = mergeOverlappingIntervals(array); console.log('result', result);Supongo que una de las ideas que podría necesitar para comprender este algoritmo es la siguiente:
Incluso cuando ya se ha insertado un intervalo en la matriz de resultados, todavía se puede modificar.
Y esto es lo que pasa. currentInterval siempre es un intervalo que ya se insertó en la matriz de resultados. Esto ya sucede antes de que comience el bucle.
Pero luego, este intervalo currentInterval posiblemente esté mutado (cuando la condición if es verdadera). Más precisamente, puede extenderse . Tal extensión es efectiva en la matriz de resultados, aunque mergedIntervals no se menciona en ninguna parte del bloque if , indirectamente se muta, porque currentInterval es su miembro.
Ilustremos esto con una simple ejecución de este algoritmo.
Entrada: [[1, 5], [3, 7]]
Justo antes de que comience el bucle tenemos esta situación:
mergedIntervals ┌─────────┬───────────────────────┐ │ index: │ 0 │ ├─────────┼───────────────────────┤ │ content:│ currentInterval │ │ │ ┌─────────┬───┬───┐ │ │ │ │ index: │ 0 │ 1 │ │ │ │ ├─────────┼───┼───┤ │ │ │ │ content:│ 1 │ 5 │ │ │ │ └─────────┴───┴───┘ │ └─────────┴───────────────────────┘ Esta visualización muestra la matriz externa con una ranura (índice 0), cuyo contenido es una matriz interna con dos ranuras (índices 0 y 1). La clave aquí es que la variable currentInterval hace referencia a una matriz que se encuentra dentro mergedIntervals .
Ahora, cuando el ciclo hace su primera iteración, realmente es una iteración inútil, porque deja que nextInterval sea el primer intervalo de los intervalos de entrada, que es el mismo intervalo que currentInterval . La condición if es verdadera, pero esa expresión Math.max tendrá el mismo valor que currentInterval[1] ya tiene: 5. Por lo tanto, es una iteración inútil, pero tampoco hace ningún daño.
La segunda iteración es la interesante. Aquí nextInterval es el segundo intervalo en la entrada: [3, 7] . La condición if es verdadera (porque 5 >= 3), por lo que currentInterval[1] obtiene el valor de nextInterval[1] , que es 7. Esto efectivamente extiende el intervalo actual y obtenemos esto:
mergedIntervals ┌─────────┬───────────────────────┐ │ index: │ 0 │ ├─────────┼───────────────────────┤ │ content:│ currentInterval │ │ │ ┌─────────┬───┬───┐ │ │ │ │ index: │ 0 │ 1 │ │ │ │ ├─────────┼───┼───┤ │ │ │ │ content:│ 1 │ 7 │ │ │ │ └─────────┴───┴───┘ │ └─────────┴───────────────────────┘¡Observe cómo esto afecta la matriz de resultados!
Si el segundo intervalo hubiera sido más pequeño de modo que estuviera completamente dentro currentInterval (por ejemplo [3, 4] ), nada cambiaría, ya que entonces la expresión Math.max seleccionaría currentInterval[1] . De hecho, eso sería lo correcto.
En este ejemplo simple, el bucle finaliza y la salida es, de hecho, lo que esperaríamos obtener.
Espero que esto aclare el algoritmo.