Sélection d’activités par fin la plus précoce
Planifier le maximum d’événements sans chevauchement
Sélection d’activités par fin la plus précoce est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Le problème de planification
Étant donné des événements avec des heures de début et de fin, la sélection d'activités consiste à trouver le plus grand nombre d'événements auxquels vous pouvez assister sans que deux d'entre eux se chevauchent. 📅
Le chevauchement signifie un conflit
Deux activités se chevauchent si l'une commence avant que l'autre se termine. Vous ne pouvez choisir qu'un événement parmi deux événements qui se chevauchent.
La règle gagnante
La clé de la méthode gloutonne consiste à toujours choisir l'événement qui se termine le plus tôt parmi ceux qui sont encore disponibles. Une fin précoce laisse le plus de place aux autres événements.
Trier selon l'heure de fin
Commencez par trier toutes les activités selon leur heure de fin. Le meilleur choix suivant est alors simplement le prochain événement de cet ordre qui reste compatible.
events.sort(key=lambda e: e[1])Suivre la dernière fin
Conservez une variable contenant l'heure de fin du dernier événement choisi. Tout nouvel événement doit commencer à cette heure ou après pour être compatible.
last_end = -1Parcourir et sélectionner
Parcourez une fois la liste triée. Si un événement commence à last_end ou après, sélectionnez-le et mettez last_end à jour avec son heure de fin.
for s, f in events:
if s >= last_end:
count += 1
last_end = fCela s'exécute en n log n
Le coût provient du tri, en O(n log n), puis d'un seul parcours linéaire. C'est suffisamment rapide, même pour de très grandes entrées de concours.
Pourquoi la fin la plus précoce l'emporte
Finir en premier libère la chronologie le plus tôt possible et ne peut donc jamais bloquer un meilleur plan. Remplacer un événement d'une solution optimale par celui-ci conserve une solution tout aussi bonne.
Le début le plus précoce échoue
Choisir selon le début le plus précoce peut vous faire sélectionner un événement très long qui monopolise toute la journée. La durée seule peut également vous induire en erreur : fiez-vous donc à l'heure de fin.
Gérer les limites qui se touchent
Déterminez si un événement qui se termine exactement quand un autre commence constitue un conflit. Utilisez s >= last_end pour autoriser les événements consécutifs.
Une forme courante des problèmes de concours
Ce motif se cache derrière de nombreuses tâches : réserver des salles, regarder des émissions ou exécuter des travaux. Identifiez-le et la règle de la fin la plus précoce s'applique.
Vérification rapide
Vous souhaitez obtenir le nombre maximal d'activités qui ne se chevauchent pas.
Récapitulatif
Triez les activités selon leur heure de fin, puis sélectionnez chacune de celles qui commencent après la fin de votre dernier choix. Un tri et un parcours suffisent à obtenir l'ensemble maximal. 🚀
Questions Fréquemment Posées
La leçon « Sélection d’activités par fin la plus précoce » est-elle gratuite ?
Oui — le texte complet de « Sélection d’activités par fin la plus précoce » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Sélection d’activités par fin la plus précoce » ?
Planifier le maximum d’événements sans chevauchement Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Sélection d’activités par fin la plus précoce » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- L’état d’esprit glouton
- Sélection d’activités par fin la plus précoce
- Sac à dos fractionnaire par ratio
- Repérer les échecs de l’approche gloutonne