Linjesveip for maksimalt overlapp
Tell samtidige intervaller ved hjelp av hendelser
Linjesveip for maksimalt overlapp er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 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.
Spørsmålet om maksimalt overlapp
Hvor mange intervaller dekker det samme tidspunktet samtidig? Det høyeste antallet er det maksimale overlappet, altså det travleste punktet på tidslinjen. 📈
Tenk i hendelser
Slutt å tenke på hele intervaller. Del hvert intervall i to hendelser: en +1 når det starter, og en -1 når det slutter.
Bygg hendelseslisten
Legg til én starthendelse og én slutthendelse i én felles liste for hvert intervall. Hver hendelse inneholder en posisjon og en delta på pluss eller minus én.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Sorter hendelsene
Sorter alle hendelsene etter posisjon, slik at De kan gå gjennom tidslinjen fra venstre mot høyre og behandle endringene i riktig rekkefølge.
events.sort()Gå gjennom og tell
Gå gjennom de sorterte hendelsene mens De holder en løpende teller. Legg til hver delta når De passerer den, så viser telleren hvor mange intervaller som er aktive akkurat nå.
active = 0
for pos, delta in events:
active += deltaFølg med på toppen
Etter hver oppdatering sammenligner De telleren med den beste verdien så langt. Den største verdien telleren noen gang når, er det maksimale overlappet.
best = max(best, active)Trikset ved likhet
Ved like posisjoner har rekkefølgen betydning. Hvis et sluttpunkt ved x skal frigjøre plassen før en start ved x, sorterer De sluttpunkter før startpunkter på samme sted.
Kod deltaene slik at de sorteres riktig
En smart måte å håndtere likheter på er å velge deltaer slik at tuppel-sorteringen gjør jobben for Dem. Plasser deltaen -1 før +1 når posisjonene er like.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieHvorfor det går raskt
De oppretter 2n hendelser, sorterer dem én gang og går gjennom dem én gang. Hele metoden har kompleksiteten O(n log n), dominert av den ene sorteringen.
Hvor De ser det
Maksimalt overlapp løser klassiske oppgaver som å finne det minste antallet rom som trengs til møter, eller det høyeste antallet samtidige brukere på en server.
Mer enn bare telling
Den samme gjennomgangen kan enkelt utvides: De kan spore den totale dekkede lengden eller finne alle posisjoner der antallet endres, alt i én lineær gjennomgang.
Rask sjekk
De går gjennom hendelser for å finne maksimalt overlapp.
Oppsummering
Gjør intervaller om til +1-starthendelser og -1-slutthendelser, sorter dem, og gå gjennom en teller for å finne toppen. Håndter likheter ved å avslutte før De starter. 🚀
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 «Linjesveip for maksimalt overlapp» gratis?
Ja – hele teksten i «Linjesveip for maksimalt overlapp» 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 «Linjesveip for maksimalt overlapp»?
Tell samtidige intervaller ved hjelp av hendelser 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 3 av 4.
Hvor lang tid tar leksjonen «Linjesveip for maksimalt overlapp»?
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