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.
- Si empieza en el final abierto o antes, estira ese final hasta el mayor de los dos finales
- Ordena los intervalos por inicio
- Si no, hay un hueco, así que abre un bloque nuevo con este intervalo
- Pon el primer intervalo en la salida como bloque abierto
- Recorre el resto comparando cada inicio con el final del bloque abierto
Mini quiz
1 / 3