Overlappende intervallen samenvoegen
Rangereeksen die elkaar raken of overlappen combineren
Overlappende intervallen samenvoegen is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 2 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.
Het doel van samenvoegen
Bij veel intervallen wil je de intervallen die elkaar raken of overlappen samenvoegen tot zo weinig mogelijk niet-overlappende bereiken. 🧩
Wanneer twee intervallen overlappen
Twee intervallen overlappen wanneer het ene begint voordat het andere eindigt. Na sorteren op het begin betekent dit dat het volgende begin kleiner dan of gelijk aan het huidige einde is.
Altijd eerst sorteren
Samenvoegen werkt alleen van links naar rechts als de intervallen geordend zijn. Begin daarom met ze te sorteren op het begin. Dit vormt de basis van de volledige doorloop.
intervals.sort(key=lambda x: x[0])Houd een huidig bereik bij
Doorloop de gesorteerde lijst en houd één huidig samengevoegd interval bij. Elk nieuw interval breidt dit uit of begint een nieuw bereik.
Breid uit bij overlap
Als het volgende begin binnen het huidige bereik valt, overlappen de intervallen. Vergroot dan het huidige einde tot het grootste van de twee eindpunten.
cur_end = max(cur_end, end)Neem het grootste einde
Gebruik voor het nieuwe einde altijd max. Een kort interval dat binnen een lang interval valt, mag het bereik dat je al hebt opgebouwd niet verkleinen.
Sluit het ene en open een nieuw bereik
Als het volgende begin na het huidige einde ligt, is er een gat. Voeg het voltooide bereik toe aan je antwoord en begin een nieuw huidig interval.
result.append([cur_start, cur_end])Vergeet het laatste niet
De lus bouwt het laatste bereik op, maar voegt het nooit toe. Voeg na het einde van de lus dat laatste huidige interval toe met append, zodat het niet verloren gaat.
Raken telt als overlap
Bepaal of [1, 3] en [3, 5] moeten worden samengevoegd. Meestal wel, dus gebruik start <= cur_end. Lees de opgave om deze randregel te bevestigen.
De volledige doorloop
Eén doorloop na het sorteren levert alle samengevoegde intervallen op, dus de hele methode draait in O(n log n) door het sorteren plus een lineaire doorloop.
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, eEen veelvoorkomende toepassing
Samenvoegen is nuttig voor agenda's en boekingssystemen: voeg drukke blokken samen om de echte vrije tijd te zien. Veel wedstrijdopgaven hebben dezezelfde vorm.
Snelle controle
Je voegt intervallen samen nadat je ze op begin hebt gesorteerd.
Samenvatting
Sorteer op begin, houd een huidig interval bij en breid uit met max bij overlap, of voeg het toe en begin opnieuw bij een gat. Vergeet de laatste toevoeging niet. 🚀
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 “Overlappende intervallen samenvoegen” gratis?
Ja — de volledige tekst van “Overlappende intervallen samenvoegen” 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 “Overlappende intervallen samenvoegen”?
Rangereeksen die elkaar raken of overlappen combineren 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 2 van 4.
Hoe lang duurt de les “Overlappende intervallen samenvoegen”?
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