Fusionner les intervalles qui se chevauchent
Combiner les plages qui se touchent ou se chevauchent
Fusionner les intervalles qui se chevauchent 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.
L'objectif de la fusion
Étant donné plusieurs intervalles, vous devez fusionner ceux qui se touchent ou se chevauchent afin d'obtenir le plus petit nombre possible de plages disjointes. 🧩
Quand deux intervalles se chevauchent
Deux intervalles se chevauchent lorsque l'un commence avant que l'autre ne se termine. Après un tri selon le début, cela signifie que le prochain début est inférieur ou égal à la fin actuelle.
Toujours commencer par trier
La fusion ne fonctionne de gauche à droite que si les intervalles sont ordonnés. Commencez donc par les trier selon leur début. C'est le fondement de tout le parcours.
intervals.sort(key=lambda x: x[0])Conserver une plage actuelle
Parcourez la liste triée en conservant un intervalle fusionné actuel. Chaque nouvel intervalle l'étend ou commence une nouvelle plage.
Étendre en cas de chevauchement
Si le prochain début se trouve dans la plage actuelle, les intervalles se chevauchent : étendez alors la fin actuelle jusqu'à la plus grande des deux fins.
cur_end = max(cur_end, end)Prendre la fin maximale
Utilisez toujours le maximum pour la nouvelle fin. Un intervalle court inclus dans un intervalle long ne doit pas réduire la plage déjà construite.
Fermer et en ouvrir une nouvelle
Si le prochain début dépasse la fin actuelle, il y a un écart. Ajoutez la plage terminée à votre réponse et commencez un nouvel intervalle actuel.
result.append([cur_start, cur_end])Ne pas oublier le dernier
La boucle construit la dernière plage, mais ne l'ajoute jamais. Une fois la boucle terminée, utilisez append pour ajouter ce dernier intervalle actuel afin de ne pas le perdre.
Le contact compte comme chevauchement
Déterminez si [1, 3] et [3, 5] doivent fusionner. C'est généralement le cas, utilisez donc start <= cur_end. Lisez l'énoncé pour confirmer cette règle aux limites.
Le balayage complet
Un seul parcours après le sort vous donne tous les intervalles fusionnés, de sorte que la méthode complète s'exécute en O(n log n) : le sort, puis un balayage linéaire.
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eUn usage courant
La fusion est utile pour les calendriers et les systèmes de réservation : regroupez les périodes occupées pour voir le véritable temps libre. De nombreux exercices de concours reprennent exactement cette structure.
Vérification rapide
Vous fusionnez les intervalles après les avoir triés par début.
Récapitulatif
Triez par début, conservez un intervalle courant et étendez-le avec le maximum en cas de chevauchement, ou ajoutez-le puis réinitialisez-le en cas de trou. N'oubliez pas le append final. 🚀
Questions Fréquemment Posées
La leçon « Fusionner les intervalles qui se chevauchent » est-elle gratuite ?
Oui — le texte complet de « Fusionner les intervalles qui se chevauchent » 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 « Fusionner les intervalles qui se chevauchent » ?
Combiner les plages qui se touchent ou se chevauchent 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 « Fusionner les intervalles qui se chevauchent » ?
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