Sorter intervaller etter start
Sorter hendelser før de behandles
Sorter intervaller etter start er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 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.
Hva et intervall er
Et intervall er ganske enkelt et par tall, en start og en slutt, for eksempel [2, 5]. De fleste intervallproblemer består av en liste med slike par. 📏
Sortering skaper orden
Rå intervaller kommer i vilkårlig rekkefølge, noe som gjør dem vanskelige å analysere. Sortering først gjør kaoset om til en ryddig gjennomgang fra venstre mot høyre.
Sorter etter start
Det vanlige er å sortere etter start-verdien. Da begynner hvert intervall på eller etter det forrige, slik at du kan gå gjennom listen én gang fremover.
intervals.sort(key=lambda x: x[0])Tupler sorteres naturlig
Hvis du lagrer intervaller som tupler, sorterer Python dem automatisk etter det første elementet og deretter det andre. Du trenger ikke engang en key-funksjon her.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Hvorfor starte med start
Sortering etter start lar deg behandle hendelser i tidsrekkefølge. Det neste intervallet kan bare begynne senere, og dette er den viktige invarianten for gjennomgangen.
Lik start
Når to intervaller har samme start, avgjør den sekundære sorteringsnøkkelen rekkefølgen. Sortering etter (start, end) plasserer de korteste først, noe som ofte er nyttig.
intervals.sort(key=lambda x: (x[0], x[1]))Noen ganger sorterer du etter slutt
Noen oppgaver, for eksempel å planlegge flest mulig hendelser, sorterer i stedet etter slutt. Velg nøkkelen ut fra hva gjennomgangen din trenger å vite.
intervals.sort(key=lambda x: x[1])Kostnaden ved sortering
Sortering tar O(n log n) tid, noe som vanligvis er rimelig og ofte dominerer disse problemene. Gjennomgangen etterpå tar bare O(n).
Hold ekstra data sammen med intervallet
Hvis hvert intervall har en id eller en vekt, må du sortere hele posten, ikke bare grensene. Nøkkelen bestemmer rekkefølgen, mens dataene følger med.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Sorter og gå gjennom
Nesten alle intervallalgoritmer følger mønsteret sorter først, gå deretter gjennom. Når rekkefølgen er riktig, blir sammenslåing, opptelling og planlegging enkle løkker.
En enkel mental modell
Se for deg intervallene som gjester som kommer til en fest. Sortering etter start stiller dem opp etter ankomsttid, slik at du kan hilse på dem én etter én.
Rask kontroll
Du skal til å slå sammen en liste med intervaller.
Oppsummering
Et intervall er et start-slutt-par, og sortering etter start gjør en uoversiktlig liste om til en ryddig gjennomgang. Sorter først, og behandle deretter intervallene fremover i O(n). 🚀
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 «Sorter intervaller etter start» gratis?
Ja – hele teksten i «Sorter intervaller etter start» 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 «Sorter intervaller etter start»?
Sorter hendelser før de behandles 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 1 av 4.
Hvor lang tid tar leksjonen «Sorter intervaller etter start»?
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