Trier les intervalles par début
Ordonner les événements avant de les traiter
Trier les intervalles par début est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 1 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.
Définition d'un intervalle
Un intervalle est simplement une paire de nombres, un début et une fin, comme [2, 5]. La plupart des problèmes d'intervalles fournissent une liste de ces paires. 📏
L'ordre clarifie tout
Les intervalles bruts arrivent dans n'importe quel ordre, ce qui les rend difficiles à analyser. Les trier d'abord transforme le désordre en un parcours propre de gauche à droite.
Trier par début
Le choix par défaut consiste à trier selon la valeur de début. Chaque intervalle commence alors au même endroit ou après le précédent, ce qui permet un seul parcours vers l'avant.
intervals.sort(key=lambda x: x[0])Les tuples se trient naturellement
Si vous stockez les intervalles sous forme de tuples, Python les trie gratuitement selon le premier élément, puis selon le deuxième. Aucune fonction clé n'est nécessaire ici.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Pourquoi commencer par le début
Trier selon le début permet de traiter les événements dans l'ordre du temps. L'intervalle suivant ne peut commencer que plus tard : c'est l'invariant essentiel du parcours.
Égalité des débuts
Lorsque deux intervalles ont le même début, la clé secondaire détermine leur ordre. Trier par (début, fin) place les plus courts en premier, ce qui est souvent utile.
intervals.sort(key=lambda x: (x[0], x[1]))Parfois, trier par fin
Certains problèmes, comme la programmation du plus grand nombre d'événements, nécessitent plutôt un tri selon la fin. Choisissez la clé correspondant aux informations dont votre parcours a besoin.
intervals.sort(key=lambda x: x[1])Le coût du tri
Le tri prend un temps en O(n log n), ce qui est peu coûteux et domine généralement ces problèmes. Le parcours qui suit ne prend que O(n).
Conserver les données associées
Si chaque intervalle possède un identifiant ou un poids, triez l'ensemble de l'enregistrement, et pas seulement les bornes. La clé contrôle l'ordre tandis que les données restent associées.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Trier, puis parcourir
Presque tous les algorithmes d'intervalles suivent le principe sort d'abord, puis parcourez. Un ordre correct suffit à transformer la fusion, le comptage et la planification en boucles simples.
Une image mentale simple
Imaginez les intervalles comme des invités arrivant à une fête. Les trier selon le début les aligne par heure d'arrivée, afin que vous puissiez les accueillir un par un.
Vérification rapide
Vous êtes sur le point de fusionner une liste d'intervalles.
Récapitulatif
Un intervalle est une paire début-fin, et trier selon le début transforme une liste désordonnée en un parcours clair. Triez d'abord, puis parcourez vers l'avant en O(n). 🚀
Questions Fréquemment Posées
La leçon « Trier les intervalles par début » est-elle gratuite ?
Oui — le texte complet de « Trier les intervalles par début » 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 « Trier les intervalles par début » ?
Ordonner les événements avant de les traiter 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 1 sur 4.
Combien de temps prend la leçon « Trier les intervalles par début » ?
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