Entrevista técnica: ¿Cómo fusionar intervalos superpuestos?

Planteamiento y alcance

Dada una lista no ordenada de intervalos cerrados intervals, donde cada elemento es [start, end] y start <= end, fusiona todas las superposiciones. Devuelve una nueva lista ordenada por start, disjunta dos a dos y que cubra exactamente los mismos puntos. Este problema utiliza intervalos cerrados, por lo que [1, 4] y [4, 5] comparten el punto 4 y deben convertirse en [1, 5]. La función no debe mutar su entrada.

Por ejemplo:

Input:  [[8, 10], [1, 3], [2, 6], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

La entrada puede estar vacía y contener intervalos duplicados, extremos negativos, intervalos de longitud cero o intervalos totalmente contenidos dentro de otros. El problema base garantiza dos extremos enteros válidos por elemento, por lo que la validación del formato de entrada queda fuera de la función de fusión. Este es un problema general de codificación de ingeniería de software. Su habilidad fundamental es convertir un orden arbitrario en uno que permita decisiones locales, demostrando luego que la decisión voraz no puede pasar por alto una conexión posterior.

Qué evalúa el entrevistador

La primera señal es si el candidato define la semántica de los intervalos. Los intervalos cerrados, los intervalos semiabiertos y una regla que fusiona rangos meramente adyacentes pueden producir condiciones diferentes. Escribir start < current_end sin especificar el contrato puede fallar en un caso con extremos compartidos.

La segunda señal es si el candidato puede explicar por qué ayuda ordenar. Tras el ordenamiento, el siguiente start no puede ser menor que el start actual. Si ya es mayor que el final del intervalo fusionado actual, cualquier start posterior también será mayor, por lo que el intervalo actual se puede emitir de forma segura. Una respuesta sólida presenta este argumento de finalización en lugar de solo decir «ordenar y recorrer».

La tercera señal es el manejo de la contención. Cuando [1, 10] se encuentra con [2, 3], el final fusionado debe ser max(10, 3). Sobrescribirlo con 3 pierde puntos cubiertos. Las superposiciones encadenadas también deben compararse con el intervalo fusionado en expansión, no solo con el intervalo de entrada original anterior.

El entrevistador también inspeccionará el contrato de mutación, la complejidad y la estrategia de validación. El ordenamiento normalmente determina el tiempo de ejecución O(n log n). Esta implementación consume un espacio de O(n) en una copia ordenada y el resultado para mantener la entrada inalterada. Las pruebas deben ir más allá del ejemplo estándar: asegurar que la entrada no cambie, que la salida esté ordenada y sea disjunta, y que los resultados aleatorizados coincidan con una implementación de referencia lenta.

Preguntas aclaratorias antes de responder

• ¿Son intervalos cerrados o semiabiertos, y se fusionan los extremos compartidos? Aquí son cerrados, por lo que la condición es next_start <= current_end. Si el producto trata la adyacencia por separado, utiliza una comparación estricta. Para [a, b), si los rangos contiguos pero no superpuestos se fusionan es una decisión independiente.
• ¿La entrada ya está ordenada por start? Una entrada ordenada solo necesita un recorrido lineal, reduciendo el tiempo a O(n). Una entrada no ordenada requiere ordenamiento o un método especializado ligado a un dominio acotado de extremos.
• ¿Puedo mutar la entrada? Si es así, ordena in-place y compacta con un puntero de escritura. Si no, copia los datos o utiliza una operación de ordenamiento que devuelva una nueva lista.
• ¿Los extremos son enteros de un rango acotado pequeño? El ordenamiento por comparación es la opción directa para valores comparables arbitrarios. Un universo pequeño de enteros puede permitir cubetas (buckets) o un arreglo de diferencias, pero su costo depende del rango de coordenadas más que únicamente de n.
• ¿Se trata de una única fusión offline o de un flujo continuo (stream)? Un flujo ordenado por start se puede fusionar y emitir en línea. Un flujo con orden arbitrario no puede finalizarse tempranamente de forma segura porque un intervalo futuro puede comenzar antes y servir de puente entre componentes existentes.
• ¿La salida solo necesita los límites o debe preservar metadatos de los intervalos? Fusionar límites no define cómo se combinan etiquetas, permisos o precios. Los metadatos requieren una regla de agregación explícita.

Estructura de respuesta en 30 segundos

«Primero confirmaré que son intervalos cerrados, que los extremos compartidos cuentan como superposición y que no puedo mutar la entrada. Copiaré y ordenaré por start y end, y luego mantendré un intervalo fusionado actual. Si el siguiente start es menor o igual que el final actual, extiendo el final al máximo de ambos finales. De lo contrario, ningún intervalo posterior podrá alcanzar al actual, por lo que lo agrego y comienzo un nuevo rango. Agrego el último rango tras el recorrido. El ordenamiento cuesta O(n log n), el recorrido cuesta O(n), y la copia ordenada más la salida consumen O(n) de espacio. El invariante de corrección es que los intervalos emitidos son definitivos y el intervalo actual es exactamente el último componente conexo aún no emitido».

Análisis detallado paso a paso

Un enfoque directo encuentra repetidamente cualquier par superpuesto, lo reemplaza por su unión y se reinicia hasta que no haya cambios. Es fácil de expresar con bucles anidados, pero un intervalo recién fusionado puede superponerse con algo ya examinado, por lo que puede requerir muchas pasadas y llegar a O(n²) o peor. Ese método es útil como oráculo de prueba para entradas pequeñas, pero es una mala solución primaria.

El ordenamiento convierte el problema global en un recorrido de izquierda a derecha. Ordena por (start, end) en orden ascendente. Mantén current = [current_start, current_end], el componente fusionado final entre los intervalos procesados que aún no se ha emitido. Para cada siguiente [start, end]:

1. Si start <= current_end, los dos intervalos cerrados se superponen, por lo que se establece current_end en max(current_end, end).
2. Si start > current_end, hay una brecha (gap). Cada start posterior es al menos start, por lo que ningún intervalo futuro puede alcanzar a current. Emítelo y comienza un nuevo intervalo actual.

El recorrido mantiene tres invariantes:

1. Los intervalos emitidos están ordenados, son disjuntos dos a dos y nunca cambiarán.
2. La unión de los intervalos emitidos y current es igual a la unión de todos los intervalos de entrada procesados.
3. current es el último componente fusionado maximal entre los intervalos procesados y el único componente que puede superponerse con el siguiente intervalo.

Los tres se cumplen tras inicializar a partir del primer intervalo ordenado. Una superposición solo extiende el extremo derecho del último componente y preserva su unión. En una brecha, el ordenamiento garantiza que cualquier start futuro quede más allá de current_end, por lo que la emisión es segura. Por inducción, los invariantes se mantienen durante todo el recorrido. Emitir current una vez más al final produce una unión equivalente en la que ningún par puede fusionarse más.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []

    ordered = sorted((start, end) for start, end in intervals)
    merged: list[list[int]] = []
    current_start, current_end = ordered[0]

    for start, end in ordered[1:]:
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append([current_start, current_end])
            current_start, current_end = start, end

    merged.append([current_start, current_end])
    return merged

sorted() construye una nueva lista ordenada, y desempaquetar tuplas no reescribe las listas internas originales, por lo que la función cumple su contrato de no mutación. El ordenamiento por comparación cuesta O(n log n) y el recorrido cuesta O(n), lo que da O(n log n) en total. La copia ordenada y una salida que puede contener los n intervalos son ambas lineales, por lo que el espacio incluyendo la salida es O(n). Si la entrada ya está ordenada, omitir el ordenamiento da un tiempo de O(n). Si se permite la mutación, un ordenamiento in-place y un puntero de escritura pueden reutilizar la entrada, aunque la implementación del ordenamiento aún podría requerir espacio de pila o búfer.

La validación debe cubrir entrada vacía, un intervalo, intervalos todos disjuntos, extremos compartidos, contención total, duplicados, extremos negativos y superposiciones encadenadas. Por ejemplo, [[1, 2], [2, 3], [3, 4]] debe convertirse en [[1, 4]]; esto detecta código que compara únicamente intervalos de entrada sin procesar adyacentes. Mantén una copia profunda y comprueba que la llamada no la modifique. Luego, genera entradas aleatorias pequeñas y compáralas con un oráculo lento que fusione repetidamente cualquier par superpuesto. La implementación anterior se probó diferencialmente en 10 000 casos aleatorios con semilla fija.

Para valores arbitrarios en un modelo de comparación, ordenar y recorrer es la respuesta general evidente. Cuando n es diminuto, la fusión repetida de pares puede ser más corta y su límite más lento puede no importar. Una entrada ya ordenada solo necesita el recorrido. Un dominio entero acotado pequeño puede justificar cubetas o una técnica de arreglo de diferencias cuyo costo dependa del universo de coordenadas. En una entrevista, presenta estos casos especiales solo cuando las restricciones lo justifiquen.

Ejemplo de respuesta de alta calidad

«Primero haré explícitos los límites: la entrada contiene intervalos cerrados no ordenados, compartir un extremo cuenta como superposición y debo devolver nuevos datos. Eso significa que [1, 4] y [4, 5] usan una prueba de menor o igual.

Una versión de fuerza bruta podría seguir buscando pares y reiniciándose, pero el intervalo recién fusionado puede superponerse con algo visto anteriormente, por lo que puede requerir muchas pasadas. Yo ordenaría por start y mantendría solo un intervalo que aún no sea definitivo. Cuando el siguiente start esté dentro de su end, lo extiendo con el end mayor. De lo contrario, lo escribo en el resultado y comienzo un nuevo componente.

La comparación importante es contra el componente acumulado, no solo contra el intervalo crudo precedente. El ordenamiento garantiza que una vez que el siguiente start supera el end actual, todos los starts posteriores también lo hacen, por lo que el resultado actual queda definitivamente finalizado. Por lo tanto, el prefijo emitido se mantiene ordenado y disjunto, mientras que el intervalo actual cubre exactamente el último componente fusionado de la entrada procesada.

Usaré sorted() para evitar modificar la lista de quien llama y retornaré anticipadamente ante una entrada vacía. El tiempo es de O(n log n) por el ordenamiento más un recorrido lineal, y la copia ordenada junto con la salida utilizan un espacio de O(n). Probaría intervalos que se tocan, anidados, duplicados, negativos y encadenados, y luego haría pruebas diferenciales contra una fusión lenta por pares, asegurando también que la entrada no cambie».

Errores comunes

• Elegir < o <= sin definir la semántica de los extremos → el resultado para extremos compartidos depende del contrato → Indica la semántica de cerrados frente a semiabiertos y si los rangos contiguos se fusionan antes de elegir la condición.
• Recorrer en el orden original → los intervalos superpuestos pueden estar muy separados y un intervalo futuro puede reconectar salidas ya emitidas → Ordena por start, a menos que se garantice una entrada ordenada.
• Comparar únicamente intervalos crudos adyacentes → el tercer elemento en [1, 10], [2, 3], [9, 12] debe encontrarse con el [1, 10] expandido → Compara siempre con el último resultado fusionado.
• Asignar current_end = end al superponerse → un intervalo contenido reduce el rango cubierto → Usa max(current_end, end).
• Olvidar el append final → un bucle que solo emite en las brechas pierde el último componente → Agrega current una vez tras finalizar el bucle.
• Leer el primer elemento en una entrada vacía → la inicialización genera un error de índice → Devuelve una lista vacía antes de ordenar e inicializar.
• Prometer no mutar pero ordenar in-place → el llamador observa la entrada reordenada y las listas internas reutilizadas pueden seguir cambiando → Usa sorted() y nuevos objetos de resultado, o haz que la mutación forme parte del contrato.
• Probar solo los arreglos esperados → superposiciones encadenadas, mutaciones y errores en los límites pueden quedar ocultos → Agrega verificaciones de propiedades y un oráculo diferencial aleatorizado.
• Afirmar que O(n log n) siempre es inevitable → la entrada ordenada y dominios enteros acotados pequeños pueden evitar el ordenamiento por comparación → Limita la afirmación del límite inferior a extremos comparables arbitrarios no ordenados.

Preguntas de seguimiento y cómo abordarlas

Pregunta de seguimiento 1: ¿Qué cambia si los extremos compartidos no cuentan como superposición?

Cambia la condición de start <= current_end a start < current_end. Confirma primero el lenguaje del dominio: los intervalos cerrados que comparten un extremo sí se intersecan matemáticamente, por lo que un producto que los mantenga separados en realidad está pidiendo fusionar solo superposiciones de longitud positiva. Para [a, b) semiabiertos, [1, 4) y [4, 5) no se superponen; fusionar rangos contiguos es entonces otra regla independiente.

Pregunta de seguimiento 2: La entrada está ordenada y se permite la mutación. ¿Cómo puedes reducir el espacio extra?

Omite el ordenamiento y compacta en el prefijo de la entrada con un puntero de escritura. Un puntero de lectura visita los nuevos intervalos. Ante una superposición, actualiza el final en la posición de escritura; ante una brecha, avanza el puntero de escritura y copia el nuevo intervalo. Devuelve la longitud del prefijo o una vista de ese prefijo. El recorrido toma un tiempo de O(n) y un espacio auxiliar de O(1) excluyendo la representación devuelta, a costa de destruir la entrada original.

Pregunta de seguimiento 3: Los intervalos llegan continuamente ordenados por start. ¿Se puede emitir un flujo (stream)?

Sí. Mantén únicamente current. Cuando un start entrante supere su final, emite current y comienza el siguiente componente; emite el último componente cuando el flujo se cierre. La memoria de trabajo es O(1) excluyendo la salida. Con un orden de llegada arbitrario, un intervalo futuro puede servir de puente entre dos componentes, por lo que la emisión temprana no es segura. En su lugar, usa un búfer, ordenamiento externo o mantén una estructura de intervalos dinámica.

Pregunta de seguimiento 4: ¿Qué ocurre si cien millones de intervalos no caben en memoria?

Utiliza un ordenamiento externo (external sort) por start: ordena lotes del tamaño de la memoria en tramos ordenados (runs), y luego realiza una fusión k-way (k-way merge). El flujo de fusión ya está ordenado por start, por lo que se ejecuta la misma máquina de estados de un solo intervalo mientras se fusiona, en lugar de materializar primero un archivo completo globalmente ordenado. El trabajo de comparación sigue siendo del orden de O(n log n); la E/S de disco y el almacenamiento temporal se convierten en los costos adicionales relevantes.

Pregunta de seguimiento 5: ¿Se pueden fusionar directamente intervalos con precios o etiquetas de permisos?

Este algoritmo solo puede unir sus límites geométricos. Si los segmentos superpuestos tienen etiquetas diferentes, reducirlos a una sola etiqueta pierde información. Define si la salida lleva un conjunto de etiquetas, la etiqueta de mayor prioridad o subsegmentos mínimos en los que los metadatos sean constantes. Esta última opción usualmente requiere un barrido sobre eventos de extremos (sweep line) en lugar de una simple unión de intervalos.