Tutte le sfide
Media 0 risolte 0% di accettazione

Simulazione della coda in banca

Simula dei clienti in attesa in un'unica fila per più sportelli bancari e riporta i tempi di attesa.

Cosa imparerai

  • Servire i clienti in ordine di arrivo (primo arrivato, primo servito)
  • Tenere traccia di quando si libera ogni sportello
  • Raccogliere statistiche di riepilogo da una simulazione

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

Esempio 1
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].

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.