Aktivitetsudvælgelse efter tidligste afslutning
Planlæg flest mulige ikke-overlappende begivenheder
Aktivitetsudvælgelse efter tidligste afslutning er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Planlægningsproblemet
Med aktiviteter, der har start- og sluttider, spørger aktivitetsudvælgelse efter det største antal aktiviteter, du kan deltage i, uden at to overlapper. 📅
Overlap betyder konflikt
To aktiviteter kolliderer, hvis den ene starter, før den anden slutter. Du kan kun vælge én aktivitet fra hvert par, der overlapper.
Den vindende regel
Det grådige nøgleprincip er altid at vælge den tilgængelige aktivitet, der slutter tidligst. En tidlig afslutning giver mest mulig plads til andre aktiviteter.
Sortér efter sluttid
Begynd med at sortere alle aktiviteter efter deres sluttid. Nu er det bedste næste valg ganske enkelt den næste aktivitet i rækkefølgen, der passer.
events.sort(key=lambda e: e[1])Hold styr på den seneste afslutning
Brug én variabel til den seneste valgte sluttid. Enhver ny aktivitet skal starte på eller efter denne værdi for at være kompatibel.
last_end = -1Gennemløb og vælg
Gå gennem den sorterede liste én gang. Hvis en aktivitet starter ved eller efter last_end, tager du den og opdaterer last_end til dens sluttid.
for s, f in events:
if s >= last_end:
count += 1
last_end = fDet kører i n log n
Omkostningen er sorteringen, O(n log n), og derefter ét lineært gennemløb. Det er hurtigt nok selv til meget store datasæt i konkurrencer.
Hvorfor den tidligste afslutning vinder
Den tidligste afslutning frigiver tidsplanen hurtigst, så den kan aldrig blokere en bedre plan. Hvis du bytter den ind i en optimal tidsplan, er den stadig lige så god.
Den tidligste start fejler
Hvis du vælger efter den tidligste start, kan du ende med én lang aktivitet, der optager hele dagen. Varigheden alene kan også vildlede dig, så stol på sluttiden.
Håndtér berøring af grænser
Beslut, om en aktivitet, der slutter præcis, når en anden begynder, tæller som en konflikt. Brug s >= last_end for at tillade aktiviteter lige efter hinanden.
Et almindeligt konkurrenceproblem
Dette mønster gemmer sig bag mange opgaver: booking af lokaler, visning af programmer eller kørsel af job. Får du øje på det, gælder reglen om tidligste afslutning.
Hurtigt tjek
Du vil have det størst mulige antal aktiviteter uden overlap.
Opsummering
Sortér aktiviteter efter sluttid, og tag derefter hver aktivitet, der starter ved eller efter, at dit seneste valg slutter. Én sortering plus ét gennemløb giver den størst mulige samling. 🚀
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Aktivitetsudvælgelse efter tidligste afslutning” gratis?
Ja — hele teksten til “Aktivitetsudvælgelse efter tidligste afslutning” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Aktivitetsudvælgelse efter tidligste afslutning”?
Planlæg flest mulige ikke-overlappende begivenheder Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Aktivitetsudvælgelse efter tidligste afslutning”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Den greedy tankegang
- Aktivitetsudvælgelse efter tidligste afslutning
- Fraktionel knapsack efter forholdstal
- Opdag, når greedy fejler