Merge Intervals

Q: ¿Cuál es la complejidad temporal de Merge Intervals?

La solución de ordenar y barrer se ejecuta en O(n log n) para n intervalos: la ordenación cuesta O(n log n) y el barrido O(n). Usa O(n) de espacio adicional para los pares ordenados y el resultado.

Q: ¿Por qué ordenar los intervalos por el inicio y no por el final?

Ordenados por el inicio, un intervalo solo puede solaparse con el grupo que estás construyendo, así que una comparación con el final de ese grupo lo decide todo. Ordenados por el final, un intervalo posterior puede empezar antes que grupos que ya cerraste: [5, 6] aparece antes que [1, 10] , y un recorrido hacia delante mantendría erróneamente 5 como inicio.

Q: ¿Puedes fusionar intervalos sin espacio adicional?

Sí, si puedes modificar la entrada. Ordena los intervalos in situ, luego escribe cada intervalo combinado al principio del mismo arreglo y conserva el índice del último que hayas escrito. El tiempo sigue siendo O(n log n), y el único espacio adicional es el que utiliza la función de ordenación de tu lenguaje.

MedioIntervalos Ordenación

+10

Recibes un conjunto de intervalos, cada uno un rango de números enteros desde un inicio hasta un final. Combina cada grupo de intervalos superpuestos en un solo intervalo que cubra todo el grupo y devuelve los intervalos combinados ordenados por inicio. Los intervalos que solo se tocan, como [1, 4] y [4, 5], se consideran superpuestos.

Los intervalos se reciben en dos arreglos de la misma longitud: el intervalo i es [starts[i], ends[i]]. Devuelves un arreglo 2D, una lista de pares [start, end].

Función

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: el inicio de cada intervalo
endsinteger-array: el final de cada intervalo, en el mismo índice que su inicio
Devuelveinteger-2d-array: los intervalos combinados como pares [start, end], ordenados por start

Restricciones

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Los intervalos llegan en cualquier orden.
Los intervalos que solo se tocan en un extremo cuentan como superpuestos.

Ejemplos

Entrada: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Salida: [[1, 7], [12, 14]]
Explicación: En orden de inicio, [1, 4] se solapa con [3, 6], que se solapa con [5, 7], así que los tres se convierten en [1, 7]. [12, 14] empieza después de 7 y se queda por su cuenta.

Para ir más allá

Los intervalos llegan ya combinados y ordenados por inicio, y debes añadir un intervalo nuevo. ¿Puedes devolver la lista combinada en tiempo O(n), sin volver a ordenarla?

Solución

Combinar pares en cualquier orden requiere pasadas repetidas, porque cada combinación amplía un intervalo y permite que alcance intervalos que ya comprobaste. En su lugar, ordénalos por el inicio. Así, un intervalo solo puede superponerse al grupo que estás construyendo, y una pasada basta para terminar.

Fusiona los pares superpuestos hasta que nada cambie

Correcto, pero no termina con las pruebas más grandes

Intuición

Los intervalos [a, b] y [c, d] se solapan cuando c ≤ b y a ≤ d, y [min(a, c), max(b, d)] cubre ambos. Cada fusión elimina un intervalo, así que el proceso se detiene y, una vez que una pasada completa no encuentra solapamientos, ningún par de intervalos restantes comparte un punto. Una pasada no es suficiente: el intervalo fusionado es más amplio y ahora puede alcanzar un intervalo con el que su parte más pequeña se comparó antes durante la pasada.

Una pasada compara aproximadamente n²/2 pares y es posible que necesites hasta n pasadas: O(n³). Una sola pasada por 10^4 intervalos ya implica 5 × 10^7 comparaciones.

Algoritmo

Copia starts y ends, y lleva la cuenta n de los intervalos activos.
Compara cada intervalo i con todos los intervalos posteriores j. Si se superponen, amplía i para que cubra j, mueve el último intervalo activo a la posición j y reduce n en uno.
Después de una fusión, vuelve a comprobar la posición j, ya que ahora hay un intervalo diferente allí.
Repite las pasadas hasta que una no realice ninguna fusión.
Empareja cada inicio activo con su final, ordena los pares por inicio y devuélvelos.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Ordena por el inicio y recorre una sola vez

Intuición

Después de ordenar por inicio, el siguiente intervalo empieza no antes que cualquier elemento del último grupo, que termina en e. Si su inicio es menor o igual que e, se solapa con el grupo o lo toca, y se une a él; e pasa a ser el mayor de los dos extremos. Si su inicio es posterior a e, ningún intervalo posterior puede volver a alcanzar el grupo, porque los intervalos siguientes empiezan más a la derecha. El grupo queda cerrado y el intervalo abre uno nuevo.

La ordenación cuesta O(n log n) y el recorrido visita cada intervalo una vez. Los grupos se cierran de izquierda a derecha, por lo que el resultado queda ordenado por inicio.

Algoritmo

Empareja cada inicio con su final: el intervalo i es [starts[i], ends[i]].
Ordena los pares por inicio.
Recorre los pares ordenados. Si el resultado está vacío o el par comienza después del final del último intervalo combinado, añade el par como un nuevo intervalo.
De lo contrario, establece el final del último intervalo combinado en el mayor de su final y el final del par.
Devuelve la lista combinada.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

Errores comunes y casos límite

Comparar con < en lugar de ≤. Los intervalos contiguos, como [1, 4] y [4, 5], deben fusionarse.
Establecer el final en el final del nuevo intervalo en lugar de usar el mayor de los dos. [1, 10] seguido de [2, 3] debe seguir siendo [1, 10].
Ordenar starts por separado y luego leer ends en las nuevas posiciones, de modo que un inicio quede asociado al final de otro intervalo. Primero empareja los valores o bien ordena los índices.
Comparar con el intervalo de entrada anterior en lugar de con el último intervalo fusionado. En [1, 10], [2, 3], [4, 5], el tercer intervalo está dentro de [1, 10], aunque no toca [2, 3].
En C, no establecer *returnSize en el número de intervalos fusionados ni el tamaño de cada columna en 2.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Merge Intervals?

La solución de ordenar y barrer se ejecuta en O(n log n) para n intervalos: la ordenación cuesta O(n log n) y el barrido O(n). Usa O(n) de espacio adicional para los pares ordenados y el resultado.

¿Por qué ordenar los intervalos por el inicio y no por el final?

Ordenados por el inicio, un intervalo solo puede solaparse con el grupo que estás construyendo, así que una comparación con el final de ese grupo lo decide todo. Ordenados por el final, un intervalo posterior puede empezar antes que grupos que ya cerraste: [5, 6] aparece antes que [1, 10], y un recorrido hacia delante mantendría erróneamente 5 como inicio.

¿Puedes fusionar intervalos sin espacio adicional?

Sí, si puedes modificar la entrada. Ordena los intervalos in situ, luego escribe cada intervalo combinado al principio del mismo arreglo y conserva el índice del último que hayas escrito. El tiempo sigue siendo O(n log n), y el único espacio adicional es el que utiliza la función de ordenación de tu lenguaje.

def mergeIntervals(starts, ends):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumentos

starts = [5, 1, 12, 3]
ends = [7, 4, 14, 6]

Salida Esperada

[[1, 7], [12, 14]]