Saltar al contenido

Merge Intervals

Lección 2 de 4 · 5 min

Merge Intervals

Paso 1 de 8

Cuatro intervalos, ya ordenados por inicio: 1–3, 2–6, 8–10, 9–11.

La idea

Ordena por inicio y luego mantén exactamente un bloque abierto.

Si el siguiente intervalo empieza en el final del bloque abierto o antes, se tocan: estira el final hasta el mayor de los dos. Si no, hay un hueco, así que cierra el bloque y abre uno nuevo. Cada intervalo se mira una sola vez.

Ejemplo del mundo real

Las paradas registradas de un conductor en su hoja de horas. Tres ventanas de GPS superpuestas en el depósito deberían leerse como un solo bloque de tiempo en el depósito, no tres: las superposiciones son ruido del sensor, y fusionarlas las convierte en el dato que de verdad facturas.

El código

Te toca

Ordena los pasos.

  1. Si empieza en el final abierto o antes, estira ese final hasta el mayor de los dos finales
  2. Ordena los intervalos por inicio
  3. Si no, hay un hueco, así que abre un bloque nuevo con este intervalo
  4. Pon el primer intervalo en la salida como bloque abierto
  5. Recorre el resto comparando cada inicio con el final del bloque abierto

Mini quiz

1 / 3

Después de ordenar, ¿cuándo se fusiona el siguiente intervalo con el bloque abierto?