Problema
Una banca ha tellers sportelli e un'unica fila d'attesa. Il cliente i arriva al minuto arrivals[i] e ha bisogno di service[i] minuti allo sportello. I clienti vengono serviti rigorosamente in ordine di arrivo (l'ordine delle liste). Quando un cliente arriva in testa alla fila, va allo sportello che si libera per primo (in caso di parità, quello con il numero più basso) e inizia nel più tardo tra il suo orario di arrivo e il momento in cui lo sportello si libera. Ogni sportello è libero dal minuto 0.
L'attesa di un cliente è il suo orario di inizio meno il suo orario di arrivo.
Implementa bank_queue_simulation(arrivals, service, tellers).
Input
arrivals: i minuti di arrivo, in ordine non decrescente.
service: i minuti di servizio di ogni cliente, nello stesso ordine.
tellers: il numero di sportelli.
Output
Restituisci [total_wait, longest_wait, last_finish]: la somma di tutte le attese, l'attesa singola più lunga e il minuto in cui finisce l'ultimo cliente. Se non ci sono clienti, restituisci [0, 0, 0].
Vincoli
0 ≤ numero di clienti ≤ 2 000
0 ≤ arrivo ≤ 100 000
1 ≤ servizio ≤ 1 000
1 ≤ tellers ≤ 20
Esempi
Input:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2
Output atteso:
expected = [4, 2, 8]
Input:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;
Output atteso:
std::vector<long long> expected = {4, 2, 8};
Input:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;
Output atteso:
long[] expected = new long[] {4, 2, 8};
Spiegazione
I clienti 1 e 2 iniziano subito (a 0 e a 1). Lo sportello 2 si libera a 4, quindi il cliente 3 aspetta 2; lo sportello 1 si libera a 5, quindi il cliente 4 aspetta 2. L'ultimo finisce a max(8, 7) = 8: [4, 2, 8].
Input:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1
Output atteso:
expected = [12, 8, 12]
Input:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;
Output atteso:
std::vector<long long> expected = {12, 8, 12};
Input:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;
Output atteso:
long[] expected = new long[] {12, 8, 12};
Spiegazione
Con un solo sportello le attese sono 0, 4 e 8, e l'ultimo cliente finisce a 12: [12, 8, 12].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Tieni un array con il minuto in cui si libera ogni sportello.
Suggerimento 2
Per ogni cliente scegli il tempo di liberazione più piccolo (a parità, l'indice più basso).
Suggerimento 3
L'inizio è il più tardo tra l'arrivo e quel momento; l'attesa è l'inizio meno l'arrivo.
Complessità attesa
tempo O(n × k), spazio aggiuntivo O(k)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.