Mínimas eliminaciones para evitar solapamientos
Planificación greedy conservando los finales más tempranos
Mínimas eliminaciones para evitar solapamientos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El objetivo de eliminación
Tiene intervalos que se solapan y quiere hacer el menor número posible de eliminaciones para que dejen de solaparse. Conserve tantos como pueda. ✂️
Invierta el problema
Hacer el menor número de eliminaciones equivale a conservar el mayor número de intervalos que no se solapen. Resuelva la versión de conservación y, después, las eliminaciones serán n menos los intervalos conservados.
Esto es selección de actividades
Conservar el mayor número de intervalos que no se solapen es, en realidad, el clásico problema de selección de actividades. La misma idea voraz resuelve ambos problemas.
Ordene por final
Aquí el orden adecuado es por tiempo de final, no de inicio. Terminar pronto libera la línea temporal lo antes posible para el siguiente intervalo que pueda conservar.
intervals.sort(key=lambda x: x[1])La elección voraz
Conserve siempre el intervalo que termine antes entre los que sigan siendo compatibles. Así deja el máximo espacio para los demás.
Siga el último final conservado
Guarde el final del último intervalo que haya conservado. El siguiente intervalo solo será compatible si su inicio es posterior o igual a ese límite.
if start >= last_end:
last_end = endCuente las eliminaciones
Cuando un intervalo comienza antes que last_end, entra en conflicto, así que descártelo y sume uno al contador de eliminaciones. En caso contrario, consérvelo.
else:
removed += 1Por qué gana el final más temprano
Una demostración por intercambio lo prueba: sustituir cualquier intervalo conservado por el intervalo compatible que termina antes nunca reduce la cantidad que puede conservar.
Gestione el caso límite del contacto
Decida si [1, 2] y [2, 3] cuentan como solapados. Si se permite compartir únicamente un extremo, use start >= last_end como prueba.
La estrategia voraz completa
Ordene por final, haga un recorrido y cuente los conflictos. El coste total es O(n log n) por la ordenación, más una única pasada lineal.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Una estructura conocida
Este patrón permite programar el mayor número de reuniones en una sala o asignar el mayor número de trabajos a una máquina. Reconózcalo siempre que haya que minimizar los conflictos.
Comprobación rápida
Conserva vorazmente los intervalos que no se solapan.
Repaso
El mínimo de eliminaciones equivale a n menos el máximo que pueda conservar. Ordene por final, conserve vorazmente los intervalos compatibles que terminen antes y cuente el resto. 🚀
Preguntas frecuentes
¿La lección «Mínimas eliminaciones para evitar solapamientos» es gratis?
Sí — el texto completo de «Mínimas eliminaciones para evitar solapamientos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Mínimas eliminaciones para evitar solapamientos»?
Planificación greedy conservando los finales más tempranos Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Mínimas eliminaciones para evitar solapamientos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Ordene intervalos por inicio
- Combine intervalos superpuestos
- Barrido lineal para el solapamiento máximo
- Mínimas eliminaciones para evitar solapamientos