Diciamo che abbiamo n lavori numerati da 1 fino a n e k lavoratori numerati da 1 fino a k.
Tutti i lavori sono ugualmente difficili, ma alcuni lavoratori sono più efficienti di altri, quindi ci viene dato il tempo necessario a ciascun lavoratore per svolgere il proprio lavoro. In effetti, non ci sono due lavoratori in grado di finire il lavoro nello stesso tempo.
All'inizio tutti gli operai si occupano del lavoro con il numero identico a loro (prima prende il primo, il secondo prende il secondo lavoro ecc.).
Se qualcuno finisce il suo lavoro, inizia a fare il lavoro con il numero più basso che nessuno ha iniziato a fare. In caso di pareggio (due o più lavoratori finiscono allo stesso tempo) il lavoratore con identificatore inferiore inizia a fare il lavoro con il numero più basso, l'altro il numero più alto.
I lavoratori lavorano fino a quando tutti i lavori sono stati eseguiti.
Per ciascun lavoratore, vorremmo restituire il numero dell'ultimo lavoro che ha completato.
Esempio:
n = 10
k = 3
efficienza dei lavoratori: 1- > 3, 2- > 5, 3- > 6
All'inizio i lavoratori uno, due, tre iniziano a fare lavori: 1,2,3.
Alla fine 3 termina il suo lavoro e inizia a fare 4.
Al tempo 5 due inizia a fare 5.
All'ora 6, l'uno e il tre finiscono il loro lavoro - iniziano rispettivamente a fare il 6 e il 7.
All'ora 9 si inizia a fare 8.
Al momento 10 due iniziano a fare 9.
E finalmente alle 12 si inizia a fare 10, l'ultimo lavoro.
Quindi la risposta è: 1- > 10, 2- > 9, 3- > 7.
È facile risolvere questo problema simulando questa procedura mantenendo una coda di priorità dei lavoratori. Il tempo di esecuzione di questo algoritmo sarebbe O (nlogn).
Mi chiedo, come risolveremo questo problema più velocemente, senza simulare, per grandi valori di n.