Activity Selection Problem
L'attività i si svolge dal momento start[i] al momento finish[i]. Una persona svolge un'attività alla volta e l'attività successiva deve iniziare strettamente dopo la fine della precedente: un'attività che inizia esattamente nel momento in cui un'altra termina non può seguirla.
Restituisci il numero massimo di attività che una persona può svolgere.
Funzione
- startinteger-array
- l'ora di inizio di ogni attività
- finishinteger-array
- l'ora di fine di ogni attività; finish[i] appartiene a start[i]
- Restituisceinteger
- il maggior numero di attività che una persona può svolgere, una dopo l'altra
Vincoli
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- Un’attività può iniziare e terminare allo stesso momento. Gli array non sono ordinati.
Esempi
- Input
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- Output
- 4
- Spiegazione
- Eseguire da 10 a 13, da 14 a 19, da 21 a 22 e da 25 a 30 dà 4. Cinque è impossibile: da 10 a 13 entra in conflitto con da 12 a 16, e da 21 a 22 con da 20 a 24.
- Input
- start = [1, 5, 9]finish = [5, 9, 12]
- Output
- 2
- Spiegazione
- L’attività dalle 5 alle 9 inizia esattamente quando termina la prima, quindi non può seguirla. Svolgere quella dalle 1 alle 5 e poi quella dalle 9 alle 12 funziona, quindi la risposta è
2.
- Input
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- Output
- 3
- Spiegazione
- L'attività da 0 a 100 si sovrappone a tutte le altre. Escludendola, 2-4, 5-7 e 8-10 si susseguono:
3.
Per approfondire
Ora due persone lavorano in parallelo, svolgendo ciascuna un’attività alla volta. Quante attività possono svolgere insieme e quale persona dovrebbe occuparsi di ciascuna?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Supponiamo che tu sappia già quale attività svolgere per prima. Quale vorresti che fosse, in modo da avere più tempo possibile a disposizione dopo?
L'attività che termina prima è sempre una scelta iniziale sicura: un piano che inizia con un'altra attività può sostituirla con quella che termina prima e mantenere lo stesso numero di attività. Dopodiché, la stessa domanda si ripete per le attività che iniziano dopo che è terminata.
Ordina le attività in base all’orario di fine, spostando ogni inizio insieme alla relativa fine. Scorri l’elenco ordinato tenendo traccia dell’orario di fine dell’ultima attività scelta e scegli ogni attività il cui inizio è strettamente maggiore di tale orario.
Soluzione
Provare ogni sottoinsieme di attività richiede un tempo esponenziale. Invece, una sola regola greedy risolve il problema: tra le attività che possono ancora essere inserite, scegli sempre quella che termina per prima. Ordinare in base all’ora di fine trasforma questa regola in un’unica scansione.
Scegli il traguardo più vicino, ancora e ancora
Corretto, ma non termina sui test più grandi
Intuizione
L'attività che termina prima di tutte è almeno una prima scelta valida quanto qualsiasi altra. Ti libera non più tardi, quindi qualsiasi attività possa seguire un'altra prima scelta può seguire anche questa, e sostituirla mantiene invariato il conteggio. Dopo questa scelta, il problema si ripete sulle attività che iniziano dopo che è terminata.
Nel primo esempio scegli da 10 a 13, poi da 14 a 19, poi da 21 a 22, poi da 25 a 30: quattro.
Ogni scelta esamina tutte le n attività, quindi il costo è n moltiplicato per la risposta. Quando tutte le 5000 attività si incastrano una dopo l'altra, si tratta di 25 milioni di controlli.
Algoritmo
- Imposta
count = 0elastFinish = -1, sotto ogni inizio. - Esamina tutte le attività per trovare quella con
start[i] > lastFinishche termina per prima. - Se non ce n'è nessuna, restituisci
count. - Altrimenti aggiungi 1 a
count, impostalastFinishsulla fine di quell'attività e ripeti la scansione.
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]Ordina per tempo di completamento e seleziona avidamente
Intuizione
Ordina una volta per orario di fine e incontrerai le attività nell’ordine in cui le scansioni qui sopra le hanno cercate. Scorri l’elenco ordinato tenendo lastFinish, l’orario di fine dell’ultima attività che hai scelto. Un’attività con start[i] > lastFinish è quella che finisce prima tra quelle che sono ancora compatibili, quindi sceglila. Qualsiasi altra entra in conflitto con la tua ultima scelta, quindi saltarla non costa nulla.
Una volta ordinato, il primo esempio diventa 10-13, 12-16, 14-19, 21-22, 20-24, 25-30. Scegli la prima, la terza, la quarta e la sesta: 12 non è dopo 13 e 20 non è dopo 22.
Non serve una regola per gli orari di fine uguali. Una volta scelta un’attività che finisce a t, tutte le altre che finiscono a t iniziano a t o prima e vengono saltate.
Algoritmo
- Ordina le attività in base a
finish, spostando ogni valore di inizio insieme al relativo valore di fine. - Imposta
count = 0elastFinish = -1. - Per ogni attività in quell’ordine, se
start[i] > lastFinish, aggiungi 1 acounte impostalastFinish = finish[i]. - Restituisci
count.
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
Trappole e casi limite
- Ordinare in base all’ora di inizio. Nel terzo esempio, l’attività da 0 a 100 inizia per prima e blocca le altre tre.
- Scegliere prima l’attività più breve. Con le attività da 1 a 5, da 5 a 6 e da 6 a 10, la più breve è da 5 a 6, che si sovrappone a entrambe le altre; le attività da 1 a 5 e da 6 a 10 ne danno 2.
- Confrontare con
≥invece che con>. Nel secondo esempio, questo restituisce 3 invece di 2. - Ordinare solo
finish. Ogni inizio deve spostarsi insieme alla propria fine, altrimenti gli inizi si abbinano alle attività sbagliate. - Inizializzare
lastFinisha 0. Un’attività singola da 0 a 1 viene quindi ignorata, perché0 > 0è falso.
Domande frequenti3
Qual è la complessità temporale del problema della selezione delle attività?
L'ordinamento per orario di fine costa O(n log n), e la scansione greedy successiva costa O(n), quindi è l'ordinamento a determinare la complessità. Se le attività sono già ordinate per orario di fine, la sola scansione risolve il problema in tempo O(n) e con spazio aggiuntivo O(1).
Che cos'è il problema delle N riunioni in una stanza?
È lo stesso problema raccontato con delle riunioni: una sala, N riunioni, e una riunione può iniziare solo dopo che la precedente è terminata. Ordina le riunioni per orario di fine e scegli ciascuna di quelle che inizia dopo la fine dell’ultima riunione scelta. Per elencare le riunioni, registra ogni indice che scegli, risolvendo i pareggi sull’orario di fine scegliendo l’indice più piccolo.
Il problema della selezione delle attività è un problema di programmazione dinamica?
Può esserlo, ma non è necessario. Una tabella delle attività ordinate per orario di fine, che contiene il numero massimo di attività che terminano con ciascuna di esse, fornisce la risposta in O(n²). La scelta greedy è sempre sicura, quindi basta un solo passaggio. La tabella diventa lo strumento giusto quando le attività hanno dei valori e vuoi massimizzarne il totale.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def maxActivities(start, finish):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
Output atteso
4