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) , ya que cada intervalo se copia o se fusiona una sola vez, y usa espacio O(n) para un resultado de hasta n+1 intervalos. Añadir el intervalo y volver a ordenar toma O(n log n) .

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 la ordena. Aquí la lista está ordenada y los intervalos antiguos nunca se tocan, así que solo el intervalo nuevo puede provocar una fusión, y los intervalos con los que se fusiona forman una secuencia. Basta con una sola pasada.

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

[a, b] y [c, d] comparten un punto exactamente cuando a ≤ d y c ≤ b . Eso cuenta los intervalos que se tocan, como [2, 4] y [4, 8] , como superpuestos, tal como requiere este problema. Para mantener separados los intervalos que se tocan, usa a < d y c < b .

MedioIntervalos

+10

Recibes intervalos ordenados por inicio en dos arreglos: el intervalo i es [starts[i], ends[i]], y no hay dos que se superpongan ni se toquen. Inserta el nuevo intervalo [newStart, newEnd], combínalo con todos los intervalos que se superpongan o se toquen con él y devuelve todos los intervalos como pares [start, end] ordenados por inicio.

Los 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. [1, 2] y [3, 4] no comparten ningún punto, así que permanecen 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, los inicios correspondientes
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 mantienen.

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, así que los tres se unen para formar [2, 9].

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

Para ir más allá

Si insertas muchos intervalos uno tras otro, ¿cómo los almacenarías 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 están ordenados y separados, 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, 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. Una pasada, sin ordenar.

Añádelo y vuelve a combinarlo todo

Intuición

Reutiliza la fusión de intervalos: añade el nuevo intervalo, ordena los n+1 intervalos por inicio y recórrelos conservando el último intervalo fusionado. Después de ordenar, un intervalo solo puede solaparse con el grupo que tiene justo antes, así que cuando el siguiente inicio es menor o igual que el final conservado, amplía el final; de lo contrario, se abre un hueco y comienza un nuevo intervalo.

La ordenación cuesta O(n log n) para corregir una lista que está desordenada en un lugar, e ignora que los intervalos antiguos nunca se fusionan entre sí.

Algoritmo

Empareja cada inicio con su final y añade [newStart, newEnd] a la lista.
Ordena los intervalos por inicio.
Recórrelos en orden, conservando el último intervalo combinado.
Si el siguiente inicio es menor o igual que el final conservado, aumenta el final conservado 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

La lista está ordenada y sus intervalos están separados, así que los intervalos que se unen al nuevo forman una secuencia continua. Todo lo que está antes de esa secuencia cumple ends[i] < newStart: termina antes de que comience el nuevo intervalo. La condición es estricta porque un intervalo que termina exactamente en newStart toca el nuevo y debe fusionarse.

Dentro de la secuencia, un intervalo con starts[i] ≤ mergedEnd se superpone al intervalo que estás construyendo o lo toca, así que lo amplía hasta el inicio menor y el final mayor. El primer intervalo que comienza después de mergedEnd pone fin a la secuencia, ya que todos los posteriores comienzan más a la derecha. Cuando la secuencia está vacía, el nuevo intervalo se agrega por sí solo. En el primer ejemplo, se copia [1, 3], [5, 7] y [10, 12] amplían [6, 11] a [5, 12], y se copia [15, 18]. Cada intervalo se examina una vez: tiempo O(n) y ningún uso de memoria aparte del 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

Desigualdades incorrectas para intervalos que se tocan. Con ends[i] ≤ newStart en el primer bucle, o starts[i] < mergedEnd en el segundo, [2, 4] y [4, 8] permanecen separados. La primera prueba es estricta; la segunda no.
Comparar con mergedEnd + 1. Eso une [1, 2] y [3, 4], que no comparten ningún punto.
Mantener newStart como inicio del intervalo combinado. [6, 11] empieza dentro de [5, 7], así que el resultado empieza en 5.
Añadir el nuevo intervalo solo cuando se solapa con alguno. Cuando cae en un espacio o más allá de cualquiera de los extremos, como ocurre con [5, 6], el bucle del medio nunca se ejecuta y, aun así, debe añadirse.
Leer starts[i] antes de comprobar i < n. Si un nuevo intervalo llega más allá del último, el índice se sale del límite.

Preguntas frecuentes3

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

La solución de una sola pasada se ejecuta en tiempo O(n), ya que cada intervalo se copia o se fusiona una sola vez, y usa espacio O(n) para un resultado de hasta n+1 intervalos. Añadir el intervalo y volver a ordenar toma O(n log n).

¿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 la ordena. Aquí la lista está ordenada y los intervalos antiguos nunca se tocan, así que solo el intervalo nuevo puede provocar una fusión, y los intervalos con los que se fusiona forman una secuencia. Basta con una sola pasada.

¿Cómo compruebas si dos intervalos se superponen?

[a, b] y [c, d] comparten un punto exactamente cuando a ≤ d y c ≤ b. Eso cuenta los intervalos que se tocan, como [2, 4] y [4, 8], como superpuestos, tal como requiere este problema. Para mantener separados los intervalos que se tocan, usa a < d y c < b.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

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