Problema
Un banco tiene tellers cajeros y una sola fila de espera. El cliente i llega en el minuto arrivals[i] y necesita service[i] minutos en la caja. Los clientes se atienden estrictamente en orden de llegada (el orden de las listas). Cuando un cliente llega al frente de la fila, pasa con el cajero que se desocupa más pronto (el de número más bajo en caso de empate) y empieza en el momento más tardío entre su hora de llegada y la hora en que ese cajero queda libre. Todos los cajeros están libres desde el minuto 0.
La espera de un cliente es su hora de inicio menos su hora de llegada.
Implementa bank_queue_simulation(arrivals, service, tellers).
Entrada
arrivals: los minutos de llegada, en orden no decreciente.
service: los minutos de atención de cada cliente, en el mismo orden.
tellers: la cantidad de cajeros.
Salida
Devuelve [total_wait, longest_wait, last_finish]: la suma de todas las esperas, la espera individual más larga y el minuto en que termina el último cliente. Si no hay clientes, devuelve [0, 0, 0].
Restricciones
0 ≤ número de clientes ≤ 2,000
0 ≤ llegada ≤ 100,000
1 ≤ atención ≤ 1,000
1 ≤ tellers ≤ 20
Ejemplos
Entrada:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2
Salida esperada:
expected = [4, 2, 8]
Entrada:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;
Salida esperada:
std::vector<long long> expected = {4, 2, 8};
Entrada:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;
Salida esperada:
long[] expected = new long[] {4, 2, 8};
Explicación
Los clientes 1 y 2 empiezan enseguida (en 0 y 1). El cajero 2 queda libre en 4, así que el cliente 3 espera 2; el cajero 1 queda libre en 5, así que el cliente 4 espera 2. El último termina en max(8, 7) = 8: [4, 2, 8].
Entrada:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1
Salida esperada:
expected = [12, 8, 12]
Entrada:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;
Salida esperada:
std::vector<long long> expected = {12, 8, 12};
Entrada:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;
Salida esperada:
long[] expected = new long[] {12, 8, 12};
Explicación
Con un solo cajero, las esperas son 0, 4 y 8, y el último cliente termina en 12: [12, 8, 12].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Lleva un arreglo con el minuto en que se desocupa cada cajero.
Pista 2
Para cada cliente, elige la hora libre más temprana (el índice más bajo en caso de empate).
Pista 3
La hora de inicio es la más tardía entre la llegada y esa hora libre; la espera es el inicio menos la llegada.
Complejidad esperada
tiempo O(n × k), espacio extra O(k)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.