Slå sammen overlappende intervaller
Kombiner intervaller som berører eller overlapper
Slå sammen overlappende intervaller er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Målet med sammenslåingen
Med mange intervaller vil du slå sammen dem som berører eller overlapper hverandre, til færrest mulig områder uten overlapp. 🧩
Når to intervaller overlapper
To intervaller overlapper når det ene starter før det andre slutter. Etter sortering etter start betyr det at den neste starten er mindre enn eller lik den nåværende slutten.
Sorter alltid først
Sammenslåing fungerer bare fra venstre mot høyre når intervallene er sortert, så begynn med å sortere dem etter start. Dette er grunnlaget for hele gjennomgangen.
intervals.sort(key=lambda x: x[0])Hold oversikt over et aktuelt område
Gå gjennom den sorterte listen mens du holder ett aktuelt sammenslått intervall. Hvert nytt intervall enten utvider det eller starter et nytt område.
Utvid ved overlapp
Hvis den neste starten ligger innenfor det nåværende området, overlapper intervallene, og du utvider den nåværende slutten til den største av de to sluttene.
cur_end = max(cur_end, end)Velg den største slutten
Bruk alltid max for den nye slutten. Et kort intervall som ligger inne i et langt, må ikke gjøre området du allerede har bygget, mindre.
Avslutt og åpne et nytt
Hvis den neste starten ligger etter den nåværende slutten, finnes det et mellomrom. Legg det ferdige området i svaret, og start et nytt aktuelt intervall.
result.append([cur_start, cur_end])Ikke glem det siste
Løkken bygger det siste området, men legger det aldri i svaret. Når løkken er ferdig, må du append det siste aktuelle intervallet, slik at det ikke går tapt.
Berøring regnes som overlapp
Avgjør om [1, 3] og [3, 5] skal slås sammen. Vanligvis skal de det, så bruk start <= cur_end. Les oppgaven for å bekrefte denne kantregelen.
Hele gjennomgangen
Én gjennomgang etter sorteringen gir alle de sammenslåtte intervallene, så metoden har totalt kompleksiteten O(n log n) fra sorteringen pluss en lineær gjennomgang.
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, eEt vanlig bruksområde
Sammenslåing er nyttig i kalendere og bookingsystemer: Slå sammen opptatte tidsblokker for å se den faktiske ledige tiden. Mange konkurranseoppgaver skjuler dette samme mønsteret.
Rask sjekk
Intervaller slås sammen etter at de er sortert etter starttidspunkt.
Oppsummering
Sorter etter starttidspunkt, hold på det gjeldende intervallet, og utvid det med maksverdien ved overlapp, eller legg det til og start på nytt ved et mellomrom. Husk å legge til det siste intervallet. 🚀
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Slå sammen overlappende intervaller» gratis?
Ja – hele teksten i «Slå sammen overlappende intervaller» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Slå sammen overlappende intervaller»?
Kombiner intervaller som berører eller overlapper Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Slå sammen overlappende intervaller»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Sorter intervaller etter start
- Slå sammen overlappende intervaller
- Linjesveip for maksimalt overlapp
- Minimalt antall fjerninger for å unngå overlapp