Balayage de ligne pour le chevauchement maximal
Compter les intervalles simultanés à l’aide d’événements
Balayage de ligne pour le chevauchement maximal est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 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.
La question du chevauchement maximal
Combien d'intervalles couvrent le même instant simultanément ? Le nombre maximal est le chevauchement maximal, le point le plus chargé de votre ligne du temps. 📈
Raisonnez en événements
Cessez de considérer les intervalles entiers. Divisez chacun en deux événements : +1 lorsqu'il commence et -1 lorsqu'il se termine.
Construisez la liste d'événements
Pour chaque intervalle, ajoutez un événement de début et un événement de fin à une même liste. Chaque événement contient une position et une variation de plus ou moins un.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Triez les événements
Triez chaque événement selon sa position afin de parcourir la ligne du temps de gauche à droite et de traiter les changements dans le bon ordre.
events.sort()Balayez et comptez
Parcourez les événements triés en conservant un compteur cumulatif. Ajoutez chaque variation au fur et à mesure ; le compteur indique alors combien d'intervalles sont actifs.
active = 0
for pos, delta in events:
active += deltaSuivez le maximum
Après chaque mise à jour, comparez le compteur avec votre meilleur résultat jusque-là. La plus grande valeur jamais atteinte par le compteur est le chevauchement maximal.
best = max(best, active)L'astuce du départage
Lorsque les positions sont égales, l'ordre est important. Si une fin en x doit libérer la place avant un début en x, triez les fins avant les débuts au même endroit.
Encodez les variations pour les trier correctement
Une manière élégante de départager les égalités consiste à choisir les variations de façon que le tri des tuples s'en charge. Placez la variation -1 avant la variation +1 lorsque les positions correspondent.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tiePourquoi cette méthode est rapide
Vous créez 2n événements, vous les triez une fois, puis vous effectuez un balayage. La méthode complète est en O(n log n), car elle est dominée par ce sort unique.
Où la rencontrer
Le chevauchement maximal permet de résoudre des exercices classiques, comme déterminer le nombre minimal de salles nécessaires pour des réunions ou le nombre maximal d'utilisateurs simultanés sur un serveur.
Au-delà du simple comptage
Le même balayage s'étend facilement : suivez la longueur totale couverte ou trouvez chaque position où le nombre change, le tout en un seul parcours linéaire.
Vérification rapide
Vous balayez les événements pour trouver le chevauchement maximal.
Récapitulatif
Transformez les intervalles en événements +1 au début et -1 à la fin, triez-les, puis balayez-les avec un compteur pour trouver le maximum. En cas d'égalité, terminez avant de commencer. 🚀
Questions Fréquemment Posées
La leçon « Balayage de ligne pour le chevauchement maximal » est-elle gratuite ?
Oui — le texte complet de « Balayage de ligne pour le chevauchement maximal » 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 « Balayage de ligne pour le chevauchement maximal » ?
Compter les intervalles simultanés à l’aide d’événements 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 3 sur 4.
Combien de temps prend la leçon « Balayage de ligne pour le chevauchement maximal » ?
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