Non-overlapping Intervals

Q: ¿Cuál es la complejidad temporal de los intervalos no solapados?

La solución voraz ordena por el final en O(n log n) y recorre los intervalos una vez, así que el total es O(n log n) con espacio O(n) para la copia ordenada. La versión de programación dinámica es O(n²) , y probar cada conjunto que se puede conservar es O(2^n) .

MedioIntervalos Voraz

+10

El intervalo i va desde starts[i] hasta ends[i]. Devuelve el número mínimo de intervalos que debes eliminar para que ninguno de los restantes se superponga. Dos intervalos que solo se tocan, cuando uno termina exactamente en el punto donde empieza el otro, no se superponen.

Función

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: el inicio de cada intervalo
endsinteger-array: el final de cada intervalo, en el mismo índice que su inicio
Devuelveinteger: el menor número de intervalos que hay que eliminar para que los restantes no se superpongan

Restricciones

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Los intervalos no están ordenados. Dos intervalos pueden ser idénticos.

Ejemplos

Entrada: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Salida: 2
Explicación: En orden de inicio, los intervalos son [1,4], [2,3], [3,6] y [5,7]. Conserva [2,3] y [3,6], que solo se tocan, y elimina los otros 2. No pueden conservarse tres: [1,4] se superpone con [2,3], y [3,6] se superpone con [5,7].

Entrada: starts = [0, 0, 0]ends = [5, 5, 5]
Salida: 2
Explicación: Los tres intervalos son [0,5], así que cualesquiera dos se solapan. Uno se queda y eliminas 2.

Entrada: starts = [4, 1, 2]ends = [6, 2, 4]
Salida: 0
Explicación: [1,2], [2,4] y [4,6] se unen de extremo a extremo y nunca se solapan, así que no eliminas nada y la respuesta es 0.

Para ir más allá

Supón que cada intervalo tiene un valor y quieres obtener el valor total más grande entre los intervalos que no se superponen. ¿Sigue funcionando conservar el intervalo que termina primero?

Solución

Eliminar el menor número de intervalos equivale a conservar el mayor número de intervalos que no se solapan: la respuesta es n menos esa cantidad. Una regla voraz permite encontrar esa cantidad en O(n log n): de los intervalos que todavía caben, conserva siempre el que termina primero.

Conserva o elimina cada intervalo

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

Intuición

Ordena los intervalos por inicio y decide para cada uno si conservarlo o eliminarlo. Puedes conservarlo solo si empieza en el momento final o después del último intervalo conservado, de modo que los intervalos conservados formen una cadena sin solapamientos. Prueba ambas opciones en cada intervalo y elige el recuento mayor; la respuesta es n menos ese valor.

Cada intervalo puede duplicar las ramas, así que n intervalos dan lugar a hasta 2^n caminos. Treinta intervalos que no se solapan ya suponen más de mil millones de llamadas, y n puede llegar hasta 5000.

Algoritmo

Ordena los intervalos por inicio, manteniendo cada inicio junto con su propio final.
Define mostKept(i, last): el mayor número de intervalos que puedes conservar desde la posición i en adelante, cuando last es el último intervalo conservado (-1 si no hay ninguno).
Al llegar al final, devuelve 0. De lo contrario, toma mostKept(i+1, last), que elimina el intervalo i.
Si el intervalo i comienza al final de last o después, prueba también 1 + mostKept(i+1, i) y conserva el valor mayor.
Devuelve n menos mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Cadena más larga con programación dinámica

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

Intuición

La búsqueda sigue planteando la misma pregunta: ¿cuál es la longitud de la cadena más larga que termina con este intervalo? Respóndela una vez por intervalo. Ordena por inicio y deja que chain[i] sea el mayor número de intervalos que puedes conservar con el intervalo i al final.

Un intervalo que puede ir justo antes de i termina en starts[i] o antes, así que empieza antes y aparece antes en el orden. Eso da chain[i] = 1 + chain[j] para el mejor j que cumpla esa condición, o 1 si ninguno encaja. En el primer ejemplo, los valores son 1, 1, 2 y 2, así que conservas 2 y eliminas 2.

El bucle doble realiza n(n-1)/2 comprobaciones: unos 12,5 millones cuando n = 5000.

Algoritmo

Ordena los intervalos por inicio, manteniendo cada inicio junto a su propio final.
Establece chain[i] = 1 para cada intervalo.
Para cada i y cada j < i con ends[j] ≤ starts[i], establece chain[i] en chain[j]+1 cuando ese valor sea mayor.
Devuelve n menos el valor más grande de chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Voraz: conserva el intervalo que termina primero

Intuición

Toma el intervalo con el menor extremo final. Cualquier solución óptima lo conserva: en cualquier conjunto máximo que puedas conservar, sustituye el intervalo más temprano por este. Termina no después, así que sigue terminando antes o justo cuando empieza el siguiente intervalo conservado, y el conjunto mantiene su tamaño sin solapamientos. Todos los intervalos que empiezan antes de su extremo final se solapan con él y deben eliminarse; lo que queda es el mismo problema con los intervalos que empiezan en ese extremo o después.

En el primer ejemplo, ordenados por extremo final, conservas [2,3], eliminas [1,4], conservas [3,6] y eliminas [5,7]. Conservar el intervalo más corto falla en [1,5], [4,7], [6,10]: [4,7] se solapa con los otros dos y requiere dos eliminaciones cuando una es suficiente.

La ordenación cuesta O(n log n) y el recorrido O(n).

Algoritmo

Ordena los intervalos por su final, manteniendo cada final junto con su propio inicio.
Conserva el primer intervalo: establece lastEnd en su final y removed en 0.
Para cada intervalo siguiente, si empieza en lastEnd o después, consérvalo y establece lastEnd en su final.
De lo contrario, suma 1 a removed.
Devuelve removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Errores comunes y casos límite

Tratar los intervalos que se tocan como si se solaparan. Con start > lastEnd en lugar de start ≥ lastEnd, la cadena [1,2], [2,4], [4,6] da 1 en vez de 0.
Ordenar por inicio y conservar el intervalo anterior cuando hay un solapamiento. Un intervalo amplio [0,100] desplaza [1,2], [3,4] y [5,6]: tres eliminaciones en lugar de una.
Comparar cada intervalo con su vecino en la lista ordenada en lugar de con el último intervalo conservado. En el primer ejemplo, [3,6] debe compararse con el final de [2,3], no con el de [1,4], que se eliminó, o el resultado es 3.
Ordenar starts y ends como dos listas independientes. Cada final debe permanecer junto a su propio inicio.
Devolver cuántos intervalos conservas en lugar de cuántos eliminas.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de los intervalos no solapados?

La solución voraz ordena por el final en O(n log n) y recorre los intervalos una vez, así que el total es O(n log n) con espacio O(n) para la copia ordenada.

La versión de programación dinámica es O(n²), y probar cada conjunto que se puede conservar es O(2^n).

¿Puedes ordenar por hora de inicio en su lugar?

Sí, con una regla diferente para los solapamientos. Recorre los intervalos por inicio y, cuando el siguiente se solape con el último intervalo conservado, cuenta una eliminación y conserva el que termine primero. Da el mismo recuento en el mismo tiempo O(n log n).

¿Es el problema de intervalos no superpuestos lo mismo que el problema de selección de actividades?

Es la otra cara del problema. La selección de actividades busca la mayor cantidad de intervalos que no se superpongan; este problema pide eliminar la menor cantidad posible, que es n menos esa cantidad. La misma regla voraz, conservar la actividad que termina primero, resuelve ambos.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

Non-overlapping Intervals

Función

Restricciones

Ejemplos

Pistas

Solución

Conserva o elimina cada intervalo

Cadena más larga con programación dinámica

Voraz: conserva el intervalo que termina primero

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares