Non-overlapping Intervals
Recibes una lista de intervalos en forma de dos arreglos: el intervalo i va desde starts[i] hasta ends[i]. Elimina la menor cantidad posible de intervalos para que ninguno de los que queden se superponga. Dos intervalos que solo se tocan, cuando uno termina exactamente en el punto donde empieza el otro, no se superponen.
Escribe una función llamada eraseOverlapIntervals que devuelva la menor cantidad de intervalos que tienes que eliminar.
Función
- 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 solapen
Restricciones
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- 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 puedes conservar tres: [1,4] se superpone con [2,3] y [3,6] se superpone con [5,7], y cualesquiera tres de los cuatro contienen uno de esos pares.
- Entrada
- starts = [0, 0, 0]ends = [5, 5, 5]
- Salida
- 2
- Explicación
- Los tres intervalos son [0,5], así que cualesquiera dos se superponen. Solo uno puede quedarse, y eliminas los otros
2.
- Entrada
- starts = [4, 1, 2]ends = [6, 2, 4]
- Salida
- 0
- Explicación
- [1,2], [2,4] y [4,6] se conectan de fin a inicio y nunca se superponen, así que no eliminas nada y la respuesta es
0.
+17 pruebas ocultas al enviar
Para ir más allá
Supón que cada intervalo también tiene un valor y quieres obtener el mayor valor total entre los intervalos que no se superponen. ¿Sigue funcionando conservar el intervalo que termina primero? ¿Qué usarías en su lugar?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
En lugar de elegir qué eliminar, piensa en qué conservar. ¿Cómo se relaciona el conjunto más grande de intervalos que puedes conservar con la respuesta?
De todos los intervalos, el que termina primero deja más espacio para el resto. Toda respuesta óptima siempre lo conserva.
Ordena los intervalos por su extremo final y recórrelos mientras recuerdas el extremo final del último intervalo que conservaste. Se conserva un intervalo que comienza en ese extremo o después; todos los demás cuentan como eliminados.
Solución
Eliminar la menor cantidad de intervalos equivale a conservar la mayor cantidad de intervalos que no se superponen, así que la respuesta es n menos ese conjunto más grande. Probar todos los conjuntos que se podrían conservar tiene una complejidad exponencial, y la programación dinámica sobre cadenas de intervalos la reduce a O(n²). Una regla voraz resuelve el problema en O(n log n): entre los intervalos que aún caben, conserva siempre el que termina primero.
Conservar o eliminar cada intervalo
Correcto, pero no termina con las pruebas más grandes
Intuición
Replantea la pregunta. Eliminar el menor número de intervalos significa conservar el mayor número de intervalos que no se solapan, y la respuesta es n menos ese número. Así que busca el conjunto más grande que puedas conservar.
Ordena los intervalos por inicio y decide para cada uno, en ese orden, si eliminarlo o conservarlo. Solo puedes conservarlo si empieza en el final del último intervalo que conservaste o después. Esa única comprobación basta: los intervalos conservados forman entonces una cadena en la que cada uno empieza en el final del anterior o después, así que no hay dos que se solapen. Prueba ambas opciones en cada intervalo y elige el mejor resultado.
En el primer ejemplo, los intervalos ordenados son [1,4], [2,3], [3,6], [5,7]. Conservar [1,4] bloquea [2,3] y [3,6], que empiezan antes de 4, y deja espacio para [5,7]: 2 conservados. Eliminar [1,4] y conservar [2,3] y después [3,6] también permite conservar 2. Ninguna rama llega a 3, así que eliminas 4-2 = 2.
Cada intervalo puede duplicar el número de ramas, así que n intervalos generan hasta 2^n rutas. Treinta intervalos que no se solapan ya implican más de mil millones de llamadas, y las pruebas llegan hasta 5000 intervalos. La recursión también tiene n niveles de profundidad: 5000 llamadas en las pruebas más grandes, por encima del límite predeterminado de Python, que es 1.000.
Algoritmo
- Ordena los intervalos por inicio, manteniendo cada inicio junto con su propio final.
- Define
mostKept(i, last): la mayor cantidad de intervalos que puedes conservar desde la posiciónien adelante, cuandolastes la posición del último intervalo conservado (-1si no hay ninguno). - Al llegar al final de la lista, devuelve
0. De lo contrario, empieza conmostKept(i+1, last), el resultado de eliminar el intervaloi. - Si el intervalo
iempieza en el final o después del intervalolast, prueba también1 + mostKept(i+1, i)y conserva el resultado mayor. - Devuelve
nmenosmostKept(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)La cadena más larga con programación dinámica
Correcto, pero no termina con las pruebas más grandes
Intuición
La búsqueda anterior responde una y otra vez a la misma pregunta: ¿cuál es la cadena más larga que termina con este intervalo? Guarda esa respuesta una vez por intervalo. Ordena por inicio y sea chain[i] el máximo número de intervalos que puedes conservar cuando el intervalo i es el último que conservas.
El intervalo conservado justo antes de i debe terminar en starts[i] o antes. Todos esos intervalos aparecen antes en el orden ordenado: comienzan antes de terminar, así que comienzan antes de starts[i]. Esto da chain[i] = 1 + chain[j] para el mejor j anterior con ends[j] ≤ starts[i], o 1 cuando no encaja ningún intervalo. El valor más grande de chain es el máximo que puedes conservar.
Para el primer ejemplo, ordenados como [1,4], [2,3], [3,6], [5,7], los valores son 1, 1, 2 y 2: [3,6] puede ir después de [2,3], y [5,7] puede ir después de [1,4] o [2,3]. La cadena más larga tiene una longitud de 2, así que eliminas 4-2 = 2.
Cada intervalo revisa todos los intervalos anteriores, lo que supone n(n-1)/2 comprobaciones. Con n = 5000, son unos 12,5 millones de comprobaciones: está bien en un lenguaje compilado, es demasiado lento en los lenguajes más lentos para las pruebas más grandes y queda muy por detrás del algoritmo voraz de abajo.
Algoritmo
- Ordena los intervalos por inicio, manteniendo cada inicio junto con su propio final.
- Establece
chain[i] = 1para cada intervalo. - Para cada
iy cadaj < iconends[j] ≤ starts[i], establecechain[i]enchain[j]+1cuando ese valor sea mayor. - Devuelve
nmenos el valor más grande dechain.
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
Fíjate en el intervalo que termina antes. Alguna solución óptima siempre lo conserva. Toma cualquier conjunto máximo de intervalos que puedas conservar y sustituye su intervalo más temprano por este. El nuevo intervalo termina no después del que reemplaza, así que sigue terminando antes o justo cuando empieza el siguiente intervalo conservado. El conjunto sigue sin solapamientos y mantiene su tamaño, por lo que conservar el intervalo que termina antes nunca te cuesta nada.
Una vez que lo conservas, todos los intervalos que empiezan antes de que termine se solapan con él y hay que eliminarlos. Lo que queda es la misma pregunta para los intervalos que empiezan en ese momento o después, así que vuelve a aplicar la misma regla. En la práctica: ordena por finalización, recorre la lista y recuerda lastEnd, el final del último intervalo conservado. Conserva un intervalo que empiece en lastEnd o después; cuenta cualquier otro intervalo como eliminado.
El primer ejemplo, ordenado por finalización, es [2,3], [1,4], [3,6], [5,7]. Conserva [2,3], así que lastEnd = 3. [1,4] empieza en 1, antes de 3: elimínalo. [3,6] empieza en 3, no antes de 3: consérvalo, lastEnd = 6. [5,7] empieza en 5, antes de 6: elimínalo. Se eliminan dos.
Otras claves parecen tentadoras, pero fallan. Ordenar por inicio conserva [0,100] cuando se solapa con [1,2], [3,4] y [5,6], y elimina tres intervalos en vez de uno. Conservar el intervalo más corto falla con [1,5], [4,7], [6,10]: el corto [4,7] se solapa con los otros dos, así que conservarlo cuesta dos eliminaciones cuando basta con una. El final es la clave que deja más espacio para todo lo que viene después.
La ordenación cuesta O(n log n) y el recorrido O(n). La copia ordenada de los intervalos ocupa un espacio de O(n).
Algoritmo
- Ordena los intervalos por su final, manteniendo cada final junto con su propio inicio.
- Conserva el primer intervalo: establece
lastEnden su final yremoveden0. - Para cada intervalo siguiente, si comienza en
lastEndo después, consérvalo y establecelastEnden 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
La mayoría de las respuestas incorrectas se deben a la clave de ordenamiento o a la comparación en un punto de contacto.
- Tratar los intervalos que se tocan como superpuestos. Con
start > lastEnden lugar destart ≥ lastEnd, la cadena [1,2], [2,4], [4,6] pierde [2,4], que empieza exactamente donde termina [1,2], y la respuesta resulta ser 1 en lugar de 0. - Ordenar por inicio y conservar siempre el intervalo anterior cuando hay un solapamiento. Un intervalo amplio [0,100] desplaza entonces [1,2], [3,4] y [5,6]. Si ordenas por inicio, conserva el que termine primero de los dos intervalos superpuestos.
- Comparar cada intervalo con el siguiente de la lista ordenada en lugar de compararlo con el último intervalo conservado. Después de eliminar [1,4], el siguiente intervalo debe compararse con el final de [2,3], no con 4.
- Ordenar
startsyendscomo dos listas separadas. Cada final debe permanecer junto a su propio inicio; de lo contrario, compararás un inicio con el final de otro intervalo. - Devolver cuántos intervalos conservas. La pregunta pide la cantidad eliminada, que es
nmenos esa cantidad.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de los intervalos no superpuestos?
La solución voraz ordena los intervalos por su extremo en O(n log n) y luego los recorre una vez en O(n), así que el total es O(n log n). La copia ordenada de los intervalos ocupa O(n) de espacio. La versión de programación dinámica es O(n²), y probar cada conjunto que se puede conservar es O(2^n).
¿Por qué ordenar por hora de finalización da como resultado la menor cantidad de eliminaciones?
El intervalo que termina primero puede reemplazar al primer intervalo de cualquier respuesta óptima sin crear un solapamiento, porque no termina más tarde. Por tanto, alguna respuesta óptima lo conserva y, después de eliminar todo lo que se solapa con él, el resto es el mismo problema con un conjunto más pequeño. Al repetir el argumento, se demuestra que cada elección voraz es segura.
¿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. Elimina el mismo número de intervalos que ordenar por final y se ejecuta en el mismo tiempo O(n log n).
¿Es lo mismo el problema de intervalos no superpuestos que el problema de selección de actividades?
Es la otra cara de la moneda. La selección de actividades busca la mayor cantidad de intervalos que no se superpongan; este problema busca eliminar la menor cantidad posible, que es n menos ese número. La misma regla voraz, conservar la actividad que termina primero, resuelve ambos problemas.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def eraseOverlapIntervals(starts, ends):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
Esperado
2