Selección de actividades por finalización más temprana
Programe el mayor número de eventos no solapados
Selección de actividades por finalización más temprana es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 2 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
El problema de la planificación
Dadas unas actividades con horas de inicio y fin, la selección de actividades busca el mayor número de actividades a las que puede asistir sin que se solapen dos. 📅
El solapamiento implica conflicto
Dos actividades entran en conflicto si una comienza antes de que termine la otra. Solo puede elegir una actividad de cada par que se solape.
La regla ganadora
La clave greedy consiste en elegir siempre la actividad que termine antes entre las que aún están disponibles. Terminar pronto deja el máximo espacio para las demás.
Ordenar por hora de finalización
Comience ordenando todas las actividades por su hora de finalización. Así, la mejor opción siguiente es simplemente la siguiente actividad de este orden que encaje.
events.sort(key=lambda e: e[1])Controlar la última finalización
Mantenga una variable para la hora de finalización de la última actividad elegida. Cualquier actividad nueva debe comenzar en ese momento o después para ser compatible.
last_end = -1Recorrer y seleccionar
Recorra la lista ordenada una vez. Si una actividad comienza en last_end o después, selecciónela y actualice last_end con su hora de finalización.
for s, f in events:
if s >= last_end:
count += 1
last_end = fSe ejecuta en n log n
El coste está en la ordenación, O(n log n), seguida de un único recorrido lineal. Es suficientemente rápido incluso para entradas de concursos muy grandes.
Por qué gana la finalización más temprana
Terminar primero libera la línea temporal lo antes posible, por lo que nunca puede bloquear un plan mejor. Intercambiar esta actividad en cualquier planificación óptima la mantiene igual de buena.
El inicio más temprano falla
Elegir según el inicio más temprano puede seleccionar una actividad larga que ocupe todo el día. La duración por sí sola también puede inducir a error, así que confíe en la hora de finalización.
Gestionar los límites coincidentes
Decida si una actividad que termina exactamente cuando comienza otra entra en conflicto. Use s >= last_end para permitir actividades consecutivas.
Un patrón habitual en concursos
Este patrón aparece en muchas tareas: reservar salas, ver programas o ejecutar trabajos. Si lo identifica, puede aplicar la regla de la finalización más temprana.
Comprobación rápida
Quiere obtener el máximo número de actividades que no se solapen.
Repaso
Ordene las actividades por hora de finalización y después elija cada una que comience cuando ya haya terminado la última seleccionada o más tarde. Una ordenación y un recorrido producen el conjunto máximo. 🚀
Preguntas frecuentes
¿La lección «Selección de actividades por finalización más temprana» es gratis?
Sí — el texto completo de «Selección de actividades por finalización más temprana» 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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Selección de actividades por finalización más temprana»?
Programe el mayor número de eventos no solapados Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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 2 de 4.
¿Cuánto tiempo toma la lección «Selección de actividades por finalización más temprana»?
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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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
- La mentalidad greedy
- Selección de actividades por finalización más temprana
- Mochila fraccionaria por proporción
- Detecte cuándo falla greedy