Insert Interval

Q: ¿Cuál es la complejidad temporal de Insert Interval?

La solución de una sola pasada se ejecuta en tiempo O(n) : cada intervalo se copia o se fusiona exactamente una vez. El resultado contiene hasta n+1 intervalos, así que ocupa O(n) espacio, y nada más crece con la entrada. Añadir el intervalo y volver a ordenar requiere O(n log n) en su lugar.

Q: ¿En qué se diferencia Insert Interval de Merge Intervals?

Merge Intervals comienza con una lista desordenada en la que cualquier intervalo puede solaparse con cualquier otro, así que primero hay que ordenarla. En Insert Interval, la lista ya está ordenada y los intervalos antiguos nunca se tocan entre sí, así que solo el nuevo intervalo puede desencadenar una fusión. Los intervalos con los que se fusiona forman una secuencia ininterrumpida, por lo que basta con una sola pasada sin ordenar.

Q: ¿Cómo compruebas si dos intervalos se superponen?

Los intervalos [a, b] y [c, d] comparten al menos un punto exactamente cuando a ≤ d y c ≤ b . Eso cuenta los intervalos que se tocan, como [2, 4] y [4, 8] , como superpuestos, que es lo que pide este problema. Si los intervalos que se tocan tuvieran que mantenerse separados, en su lugar usarías a < d y c < b .

Q: ¿Puede la búsqueda binaria hacer que Insert Interval sea más rápido?

La búsqueda binaria encuentra dónde empieza y termina el tramo fusionado en O(log n) , porque tanto los inicios como los finales están ordenados. Sin embargo, la función sigue devolviendo una lista nueva, y copiar los intervalos sin cambios en ella cuesta O(n) . Así que el total sigue siendo O(n) . La búsqueda binaria resulta útil cuando los intervalos están en una estructura que puede eliminar e insertar un rango sin copiarlo, como un árbol equilibrado.

MedioIntervalos

+10

Recibes una lista de intervalos ordenados por inicio, dados como dos matrices de la misma longitud: el intervalo i es [starts[i], ends[i]]. Ninguno de ellos se superpone ni se toca. También recibes un intervalo nuevo, [newStart, newEnd]. Insértalo, combínalo con todos los intervalos con los que se superponga o toque y devuelve todos los intervalos como una matriz 2D de pares [start, end], ordenados por inicio.

Dos intervalos se tocan cuando uno termina donde empieza el otro, como ocurre con [2, 4] y [4, 8], y los intervalos que se tocan se combinan en uno solo. [1, 2] y [3, 4] no comparten ningún punto, así que se mantienen separados.

Función

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: el inicio de cada intervalo, en orden creciente
endsinteger-array: el final de cada intervalo, haciendo coincidir los inicios
newStartinteger: el inicio del intervalo que se va a insertar
newEndinteger: el final del intervalo que se va a insertar
Devuelveinteger-2d-array: los intervalos después de la inserción como pares [start, end], ordenados por start

Restricciones

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: los intervalos están ordenados por inicio, y ninguno se superpone ni toca a otro.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Ejemplos

Entrada: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Salida: [[1, 3], [5, 12], [15, 18]]
Explicación: [6, 11] se superpone con [5, 7] y [10, 12], así que los tres se convierten en [5, 12]. [1, 3] termina antes de 6 y [15, 18] empieza después de 12, así que ambos se quedan como están.

Entrada: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Salida: [[2, 9]]
Explicación: [4, 8] toca [2, 4] en 4 y [8, 9] en 8. El contacto cuenta como solapamiento, así que los tres se unen en [2, 9].

Entrada: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Salida: [[1, 2], [5, 6], [9, 10]]
Explicación: [5, 6] está en el espacio entre 2 y 9 y no toca a ninguno de los intervalos vecinos, así que se inserta entre ellos y no se fusiona nada.

+20 pruebas ocultas al enviar

Para ir más allá

Supongamos que insertas muchos intervalos nuevos, uno tras otro, en la misma lista. ¿Cómo almacenarías los intervalos para que cada inserción cueste O(log n) más un paso por cada intervalo antiguo que absorba?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Los intervalos anteriores ya están separados y ordenados, así que solo el nuevo intervalo puede provocar una fusión. Eso divide la lista en tres grupos: intervalos que terminan antes de que empiece el nuevo, intervalos que se solapan o lo tocan, e intervalos que empiezan después de que termine. Copia el primer grupo, combina el grupo del medio en un solo intervalo y copia el último grupo. Una pasada, sin ordenar.

Añádelo y vuelve a combinarlo todo

Intuición

Si has resuelto Merge Intervals, puedes reutilizarlo aquí. Añade el nuevo intervalo a la lista, ordena los n+1 intervalos por el inicio y fusiónalos. Después de ordenar, un intervalo solo puede solaparse con el grupo que tiene justo antes, así que recorres la lista guardando el último intervalo fusionado. Cuando el siguiente inicio es menor o igual que su final, amplía el final. De lo contrario, hay un espacio real y comienza un intervalo nuevo.

Pruébalo con el primer ejemplo. La lista queda así: [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] queda separado, porque 5 es mayor que 3. 6 es menor o igual que 7, así que [5, 7] se amplía a [5, 11]. 10 es menor o igual que 11, así que se amplía a [5, 12]. 15 es mayor que 12, así que [15, 18] inicia un intervalo nuevo.

Esto es correcto y, con 2000 intervalos, se ejecuta rápido. Sin embargo, descarta dos datos que te dieron: la lista ya está ordenada y los intervalos antiguos nunca se fusionan entre sí. Pagar O(n log n) para volver a ordenar una lista que solo está desordenada en un lugar es el paso que un entrevistador te pedirá eliminar.

Algoritmo

Empareja cada inicio con su final y añade [newStart, newEnd] a la lista.
Ordena los intervalos por inicio.
Recórrelos en orden, manteniendo el último intervalo combinado.
Si el siguiente inicio es menor o igual que el final mantenido, actualiza ese final al mayor de los dos finales.
De lo contrario, añade el siguiente intervalo como uno nuevo combinado. Devuelve la lista combinada.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Una pasada en tres partes

Intuición

Recorre la lista una vez con un índice i y divídela en tres segmentos. Primero, todos los intervalos con ends[i] < newStart terminan antes de que empiece el nuevo, así que no comparten ningún punto con él: cópialos al resultado. La prueba usa < estrictamente porque un intervalo que termina exactamente en newStart toca el nuevo y debe fusionarse.

Segundo, todos los intervalos con starts[i] ≤ mergedEnd se superponen o tocan el intervalo que estás construyendo. Incorpóralos: mergedStart pasa a ser el inicio menor y mergedEnd, el final mayor. Los intervalos de este segmento están uno junto al otro porque la lista está ordenada. Una vez que un intervalo empieza después de mergedEnd, todos los siguientes empiezan aún más a la derecha, así que nada de lo que viene después puede fusionarse. Añade el intervalo fusionado; este paso también cubre el caso en que el segmento está vacío y el nuevo intervalo se añade por sí solo.

Tercero, copia todo lo que queda. Esos intervalos empiezan después del final del intervalo fusionado y ya estaban separados entre sí.

Recorre el primer ejemplo. [1, 3] termina antes de 6: cópialo. [5, 7] empieza en 5, que es como máximo 11: el intervalo fusionado pasa a ser [5, 11]. [10, 12] empieza en 10, como máximo 11: pasa a ser [5, 12]. [15, 18] empieza después de 12, así que añade [5, 12] y copia [15, 18]. Cada intervalo se examina una sola vez, así que el tiempo es O(n) y la única memoria adicional es el propio resultado.

Algoritmo

Copia los intervalos al resultado mientras ends[i] < newStart.
Establece mergedStart = newStart y mergedEnd = newEnd.
Mientras starts[i] ≤ mergedEnd, establece mergedStart en el inicio menor y mergedEnd en el final mayor, y continúa.
Añade [mergedStart, mergedEnd].
Copia los intervalos restantes y devuelve el resultado.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Errores comunes y casos límite

El bucle es corto, así que la mayoría de los errores se deben a una comparación incorrecta o a olvidar un caso en los extremos de la lista.

Usar la desigualdad incorrecta para los intervalos que se tocan. Con ends[i] ≤ newStart en el primer bucle, o starts[i] < mergedEnd en el segundo, [2, 4] y [4, 8] quedan separados. Los intervalos que se tocan se fusionan, así que la primera prueba es estricta y la segunda no.
Fusionar intervalos que solo parecen adyacentes. [1, 2] y [3, 4] no tienen puntos en común, así que comparar con mergedEnd + 1 une intervalos que deberían permanecer separados.
Mantener newStart como el inicio fusionado. Cuando el nuevo intervalo comienza dentro de uno anterior, como ocurre con [6, 11] dentro de [5, 7], el resultado empieza en 5. Toma el menor de los dos inicios.
Agregar el nuevo intervalo solo cuando se superpone con alguno. Cuando queda antes de todos los intervalos, después de todos o en un espacio entre ellos, el bucle del medio no se ejecuta y, aun así, hay que agregar el nuevo intervalo.
Leer starts[i] o ends[i] antes de comprobar i < n. Cuando el nuevo intervalo llega más allá del último intervalo, el índice se sale de los límites de los arreglos.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Insert Interval?

La solución de una sola pasada se ejecuta en tiempo O(n): cada intervalo se copia o se fusiona exactamente una vez. El resultado contiene hasta n+1 intervalos, así que ocupa O(n) espacio, y nada más crece con la entrada. Añadir el intervalo y volver a ordenar requiere O(n log n) en su lugar.

¿En qué se diferencia Insert Interval de Merge Intervals?

Merge Intervals comienza con una lista desordenada en la que cualquier intervalo puede solaparse con cualquier otro, así que primero hay que ordenarla. En Insert Interval, la lista ya está ordenada y los intervalos antiguos nunca se tocan entre sí, así que solo el nuevo intervalo puede desencadenar una fusión. Los intervalos con los que se fusiona forman una secuencia ininterrumpida, por lo que basta con una sola pasada sin ordenar.

¿Cómo compruebas si dos intervalos se superponen?

Los intervalos [a, b] y [c, d] comparten al menos un punto exactamente cuando a ≤ d y c ≤ b. Eso cuenta los intervalos que se tocan, como [2, 4] y [4, 8], como superpuestos, que es lo que pide este problema. Si los intervalos que se tocan tuvieran que mantenerse separados, en su lugar usarías a < d y c < b.

¿Puede la búsqueda binaria hacer que Insert Interval sea más rápido?

La búsqueda binaria encuentra dónde empieza y termina el tramo fusionado en O(log n), porque tanto los inicios como los finales están ordenados. Sin embargo, la función sigue devolviendo una lista nueva, y copiar los intervalos sin cambios en ella cuesta O(n). Así que el total sigue siendo O(n). La búsqueda binaria resulta útil cuando los intervalos están en una estructura que puede eliminar e insertar un rango sin copiarlo, como un árbol equilibrado.

Python

def insertInterval(starts, ends, newStart, newEnd):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Esperado

[[1, 3], [5, 12], [15, 18]]