Suppressions minimales pour éviter les chevauchements
Planifier en conservant gloutonnement les fins les plus précoces
Suppressions minimales pour éviter les chevauchements est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 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.
L'objectif des suppressions
Vous avez des intervalles qui se chevauchent et vous voulez effectuer le moins possible de suppressions pour qu'ils ne se chevauchent plus. Conservez-en autant que possible. ✂️
Inversez le problème
Effectuer le moins de suppressions revient à conserver le plus grand nombre d'intervalles qui ne se chevauchent pas. Résolvez la version où vous devez conserver les intervalles ; le nombre de suppressions sera ensuite égal à n moins le nombre conservé.
Il s'agit de la sélection d'activités
Conserver le plus grand nombre d'intervalles qui ne se chevauchent pas revient au classique problème de sélection d'activités. La même idée gloutonne résout les deux problèmes.
Triez par fin
Ici, l'ordre gagnant se fait selon l'heure de fin, et non selon le début. Finir tôt libère la ligne du temps le plus rapidement possible pour le prochain intervalle que vous pourriez conserver.
intervals.sort(key=lambda x: x[1])Le choix glouton
Conservez toujours, parmi les intervalles encore compatibles, celui qui se termine le plus tôt. Il laisse le maximum de place pour les autres.
Suivez la dernière fin conservée
Conservez la fin du dernier intervalle que vous avez gardé. L'intervalle suivant n'est compatible que si son début est supérieur ou égal à cette limite.
if start >= last_end:
last_end = endComptez les suppressions
Lorsqu'un intervalle commence avant last_end, il entre en conflit : vous l'écartez et augmentez de un le compteur de suppressions. Sinon, vous le conservez.
else:
removed += 1Pourquoi la fin la plus précoce l'emporte
Un argument d'échange le prouve : remplacer n'importe quel intervalle conservé par l'intervalle compatible qui se termine le plus tôt ne réduit jamais le nombre d'intervalles que vous pouvez conserver.
Gérez le cas du contact
Déterminez si [1, 2] et [2, 3] sont considérés comme se chevauchant. Si le partage d'une extrémité est autorisé, utilisez start >= last_end comme vérification.
La méthode gloutonne complète
Triez par fin, effectuez un seul balayage et comptez les conflits. Le coût total est de O(n log n) pour le sort, auquel s'ajoute un seul parcours linéaire.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Une structure familière
Cette structure permet de programmer le plus grand nombre de réunions dans une salle ou de placer le plus grand nombre de tâches sur une machine. Repérez-la dès qu'il faut minimiser les conflits.
Vérification rapide
Vous conservez gloutonnement les intervalles qui ne se chevauchent pas.
Récapitulatif
Le nombre minimal de suppressions vaut n moins le nombre maximal d'intervalles que vous pouvez conserver. Triez par fin, conservez gloutonnement les intervalles compatibles qui se terminent le plus tôt, puis comptez les autres. 🚀
Questions Fréquemment Posées
La leçon « Suppressions minimales pour éviter les chevauchements » est-elle gratuite ?
Oui — le texte complet de « Suppressions minimales pour éviter les chevauchements » 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 « Suppressions minimales pour éviter les chevauchements » ?
Planifier en conservant gloutonnement les fins les plus précoces 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 4 sur 4.
Combien de temps prend la leçon « Suppressions minimales pour éviter les chevauchements » ?
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
- Trier les intervalles par début
- Fusionner les intervalles qui se chevauchent
- Balayage de ligne pour le chevauchement maximal
- Suppressions minimales pour éviter les chevauchements