Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Simulación de la fila de un banco

Simula a los clientes que esperan en una sola fila para ser atendidos por varios cajeros y reporta los tiempos de espera.

Lo que aprenderás

  • Atender a los clientes por orden de llegada
  • Llevar la cuenta de cuándo se desocupa cada cajero
  • Reunir estadísticas de resumen de una simulación

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.