Aktivitetsutvalg etter tidligste slutt
Planlegg flest mulig aktiviteter som ikke overlapper
Aktivitetsutvalg etter tidligste slutt er en gratis leksjon i Competitive Programming Academy 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 Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Planleggingsproblemet
Gitt hendelser med start- og sluttidspunkt ber aktivitetsutvelgelse deg finne det største antallet hendelser du kan delta på uten at to overlapper. 📅
Overlapp betyr konflikt
To aktiviteter kolliderer hvis den ene starter før den andre slutter. Du kan bare velge én hendelse fra hvert overlappende par.
Den vinnende regelen
Nøkkelen i den grådige løsningen er alltid å velge hendelsen som slutter tidligst blant dem som fortsatt er tilgjengelige. En tidlig slutt gir mest mulig plass til andre.
Sorter etter sluttid
Start med å sortere alle aktivitetene etter sluttidspunktet. Nå er det beste neste valget ganske enkelt den neste aktiviteten i denne rekkefølgen som passer.
events.sort(key=lambda e: e[1])Følg med på siste sluttid
Bruk én variabel for sluttidspunktet til den siste valgte aktiviteten. En ny hendelse må starte på eller etter denne verdien for å være kompatibel.
last_end = -1Gå gjennom og velg
Gå gjennom den sorterte listen én gang. Hvis en hendelse starter på eller etter last_end, velger du den og oppdaterer last_end til sluttidspunktet.
for s, f in events:
if s >= last_end:
count += 1
last_end = fDet kjører på n log n
Kostnaden er sorteringen, O(n log n), etterfulgt av én lineær gjennomgang. Det er raskt nok selv for svært store inndata i konkurranseoppgaver.
Hvorfor tidligste slutt vinner
Den som slutter først, frigjør tidslinjen tidligst, så den kan aldri blokkere en bedre plan. Hvis du bytter den inn i en optimal plan, er planen fortsatt like god.
Tidligste start mislykkes
Hvis du velger etter tidligste start, kan du ende opp med én lang hendelse som beslaglegger hele dagen. Varigheten alene kan også villede deg, så stol på sluttidspunktet.
Håndter berøringer ved grenser
Avgjør om en hendelse som slutter nøyaktig når en annen begynner, skal regnes som en konflikt. Bruk s >= last_end for å tillate hendelser rett etter hverandre.
En vanlig oppgavevariant
Dette mønsteret skjuler seg bak mange oppgaver: bestilling av rom, visning av programmer eller kjøring av jobber. Gjenkjenn det, så kan regelen om tidligste slutt brukes.
Hurtigsjekk
Du vil finne maksimalt antall aktiviteter som ikke overlapper.
Oppsummering
Sorter aktivitetene etter sluttidspunkt, og velg deretter hver aktivitet som starter etter at den siste valgte aktiviteten slutter. Én sortering pluss én gjennomgang gir den største mulige mengden. 🚀
Lær deg Python 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
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Aktivitetsutvalg etter tidligste slutt» gratis?
Ja – hele teksten i «Aktivitetsutvalg etter tidligste slutt» 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 Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Aktivitetsutvalg etter tidligste slutt»?
Planlegg flest mulig aktiviteter som ikke overlapper Du øver på Competitive Programming Academy 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 Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy 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 «Aktivitetsutvalg etter tidligste slutt»?
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 Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-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
- Den grådige tankemåten
- Aktivitetsutvalg etter tidligste slutt
- Fraksjonell ryggsekk etter forholdstall
- Oppdag når grådige løsninger feiler