Intervallen op begin sorteren
Gebeurtenissen ordenen voordat u ze verwerkt
Intervallen op begin sorteren is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat een interval is
Een interval is gewoon een paar getallen: een begin en een einde, zoals [2, 5]. De meeste intervalproblemen bestaan uit een lijst van zulke paren. 📏
Ordening brengt overzicht
Onbewerkte intervallen komen in willekeurige volgorde binnen, waardoor ze lastig te analyseren zijn. Door ze eerst te sorteren verandert de chaos in een overzichtelijke doorloop van links naar rechts.
Sorteer op het begin
De standaardaanpak is sorteren op de waarde van het begin. Elk interval begint dan op of na het interval ervoor, zodat je één keer vooruit kunt doorlopen.
intervals.sort(key=lambda x: x[0])Tupels worden vanzelf gesorteerd
Als je intervallen als tupels opslaat, sorteert Python ze vanzelf op het eerste element en daarna op het tweede. Hier heb je zelfs geen sleutelfunctie nodig.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Waarom je met het begin sorteert
Sorteren op het begin laat je gebeurtenissen in tijdvolgorde verwerken. Het volgende interval kan alleen later beginnen, en dat is de belangrijkste invariant voor de doorloop.
Gelijke beginpunten
Wanneer twee intervallen hetzelfde begin hebben, bepaalt de tweede sleutel hun volgorde. Sorteren op (start, end) zet kortere intervallen eerst, wat vaak helpt.
intervals.sort(key=lambda x: (x[0], x[1]))Soms sorteer je op het einde
Bij sommige problemen, zoals het plannen van de meeste gebeurtenissen, sorteer je juist op het einde. Kies de sleutel die past bij wat je doorloop moet weten.
intervals.sort(key=lambda x: x[1])De kosten van sorteren
Sorteren kost O(n log n) tijd. Dat is goedkoop en bepaalt meestal de kosten van deze problemen. De daaropvolgende doorloop kost slechts O(n).
Houd extra gegevens eraan vast
Als elk interval een id of gewicht bevat, sorteer dan het volledige gegevensrecord, niet alleen de grenzen. De sleutel bepaalt de volgorde, terwijl de gegevens eraan vast blijven zitten.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Eerst sorteren, daarna doorlopen
Bij vrijwel elk intervalalgoritme geldt: eerst sorteren, daarna doorlopen. Als de volgorde klopt, worden samenvoegen, tellen en plannen eenvoudige lussen.
Een snel denkmodel
Stel je de intervallen voor als gasten die op een feest aankomen. Door ze op het begin te sorteren, staan ze in volgorde van aankomst, zodat je ze één voor één kunt begroeten.
Snelle controle
Je staat op het punt een lijst met intervallen samen te voegen.
Samenvatting
Een interval is een paar met een begin en einde. Sorteren op het begin verandert een rommelige lijst in een overzichtelijke doorloop. Sorteer eerst en verwerk daarna alles vooruit in O(n). 🚀
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Intervallen op begin sorteren” gratis?
Ja — de volledige tekst van “Intervallen op begin sorteren” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Intervallen op begin sorteren”?
Gebeurtenissen ordenen voordat u ze verwerkt Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Intervallen op begin sorteren”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Intervallen op begin sorteren
- Overlappende intervallen samenvoegen
- Line sweep voor maximale overlap
- Minimaal aantal verwijderingen zonder overlap