[Leetcode] 0435. Intervalos no superpuestos

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Dada una serie de intervalos intervalos dónde intervalos[i] = [inicio _i , final _i ], devolver el número mínimo de intervalos que necesita eliminar para que el resto de los intervalos no se superpongan.

Ejemplo 1:

Aporte: intervalos = [[1,2],[2,3],[3,4],[1,3]]
Producción: 1
Explicación: [1,3] se puede eliminar y el resto de los intervalos no se superponen.

Ejemplo 2:

Aporte: intervalos = [[1,2],[1,2],[1,2]]
Producción: 2
Explicación: Debe eliminar dos [1,2] para que el resto de los intervalos no se superpongan.

Ejemplo 3:

Aporte: intervalos = [[1,2],[2,3]]
Producción: 0
Explicación: No es necesario eliminar ninguno de los intervalos ya que ya no se superponen.

Restricciones:

1 <= intervalos.longitud <= 10 ⁵
intervalos[i].longitud == 2
-5 * 10 ⁴ <= inicio _i < final _i <= 5 * 10 ⁴

Pitón

				
					Complejidad de tiempo de #: O(nlogn) Complejidad de espacio de #: O(n) al escribir clase de lista de importación Solución: def eraseOverlapIntervals(self, intervalos: Lista[Lista[int]]) -> int: intervalos.sort(key=lambda x : x[1]) k = -float("inf") ans = 0 para x, y en intervalos: if x >= k: k = y else: ans += 1 return ans intervalos = [[1, 2] , [2, 3], [3, 4], [1, 3]] print(Solución().eraseOverlapIntervals(intervalos))

Medio

Pitón

Artículos relacionados