Selezione delle attività in base alla fine più anticipata
Pianificare il maggior numero di eventi non sovrapposti
Selezione delle attività in base alla fine più anticipata è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Il problema della pianificazione
Dati eventi con orari di inizio e fine, la selezione delle attività chiede di determinare il maggior numero di eventi a cui può partecipare senza sovrapposizioni. 📅
La sovrapposizione indica un conflitto
Due attività entrano in conflitto se una inizia prima che l'altra finisca. Può scegliere un solo evento tra due eventi sovrapposti.
La regola vincente
La chiave greedy consiste nello scegliere sempre l'evento che finisce prima tra quelli ancora disponibili. Un termine anticipato lascia più spazio agli altri eventi.
Ordinare per orario di fine
Inizi ordinando tutte le attività in base al loro orario di fine. A questo punto, la scelta successiva migliore è semplicemente il primo evento in quest'ordine che sia compatibile.
events.sort(key=lambda e: e[1])Tenere traccia dell'ultima fine
Mantenga una variabile per l'orario di fine dell'ultima attività scelta. Ogni nuovo evento deve iniziare in corrispondenza o dopo questo valore per essere compatibile.
last_end = -1Scorrere e selezionare
Scorra una volta la lista ordinata. Se un evento inizia in corrispondenza o dopo last_end, lo scelga e aggiorni last_end con il suo orario di fine.
for s, f in events:
if s >= last_end:
count += 1
last_end = fRichiede n log n
Il costo principale è l'ordinamento, O(n log n), seguito da un'unica scansione lineare. È sufficientemente veloce anche per input di gara molto grandi.
Perché vince la fine più anticipata
Finire per primi libera la linea temporale prima possibile, quindi non può impedire una soluzione migliore. Sostituendo questa attività in qualsiasi pianificazione ottimale, la soluzione rimane altrettanto valida.
L'inizio più anticipato non funziona
Scegliere in base all'inizio più anticipato può portare a selezionare un evento molto lungo che occupa l'intera giornata. Anche la sola durata può trarre in inganno, quindi si affidi all'orario di fine.
Gestire gli estremi coincidenti
Decida se un evento che termina esattamente quando un altro inizia debba essere considerato in conflitto. Utilizzi s >= last_end per consentire eventi consecutivi.
Una forma comune nei problemi di gara
Questo schema si nasconde dietro molti problemi: prenotare stanze, guardare programmi o eseguire processi. Lo riconosca e potrà applicare la regola della fine più anticipata.
Verifica rapida
Vuole ottenere il numero massimo di attività non sovrapposte.
Riepilogo
Ordini le attività per orario di fine, poi scelga ogni attività che inizia dopo la fine dell'ultima selezionata. Un ordinamento e una scansione sono sufficienti per ottenere l'insieme massimo. 🚀
Domande Frequenti
La lezione «Selezione delle attività in base alla fine più anticipata» è gratuita?
Sì — il testo completo di «Selezione delle attività in base alla fine più anticipata» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Selezione delle attività in base alla fine più anticipata»?
Pianificare il maggior numero di eventi non sovrapposti Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Selezione delle attività in base alla fine più anticipata»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- La mentalità greedy
- Selezione delle attività in base alla fine più anticipata
- Knapsack frazionario per rapporto
- Riconoscere quando il greedy fallisce