Todos os desafios
Médio 0 resolvidos 0% de aceitação

Simulação de fila de banco

Simule clientes esperando em uma única fila por vários caixas de banco e informe os tempos de espera.

O que você vai aprender

  • Atender clientes por ordem de chegada
  • Acompanhar quando cada atendente fica livre
  • Coletar estatísticas de resumo de uma simulação

Problema

Ver original (inglês)

Um banco tem tellers caixas e uma única fila de espera. O cliente i chega no minuto arrivals[i] e precisa de service[i] minutos no caixa. Os clientes são atendidos estritamente por ordem de chegada (a ordem das listas). Quando um cliente chega ao início da fila, ele vai para o caixa que fica livre mais cedo (em caso de empate, o de menor número) e começa a ser atendido no maior entre o seu horário de chegada e o horário em que esse caixa fica livre. Todo caixa está livre a partir do minuto 0.

A espera de um cliente é o horário de início do atendimento menos o horário de chegada.

Implemente bank_queue_simulation(arrivals, service, tellers).

Entrada

arrivals: os minutos de chegada, em ordem não decrescente.

service: os minutos de atendimento de cada cliente, na mesma ordem.

tellers: o número de caixas.

Saída

Retorne [total_wait, longest_wait, last_finish]: a soma de todas as esperas, a maior espera individual e o minuto em que o último cliente termina. Sem clientes, retorne [0, 0, 0].

Restrições

0 ≤ número de clientes ≤ 2000

0 ≤ chegada ≤ 100 000

1 ≤ atendimento ≤ 1000

1 ≤ tellers ≤ 20

Exemplos

Exemplo 1
Entrada:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

Saída 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;

Saída 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;

Saída esperada:
long[] expected = new long[] {4, 2, 8};

Explicação

Os clientes 1 e 2 começam na hora (0 e 1). O caixa 2 fica livre em 4, então o cliente 3 espera 2; o caixa 1 fica livre em 5, então o cliente 4 espera 2. O último término é max(8, 7) = 8: [4, 2, 8].

Exemplo 2
Entrada:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

Saída 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;

Saída 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;

Saída esperada:
long[] expected = new long[] {12, 8, 12};

Explicação

Com um só caixa, as esperas são 0, 4 e 8, e o último cliente termina em 12: [12, 8, 12].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Mantenha um array com o minuto em que cada caixa fica livre.

Dica 2

Para cada cliente, escolha o menor horário livre (o menor índice em caso de empate).

Dica 3

O início é o maior entre a chegada e esse horário livre; a espera é o início menos a chegada.

Complexidade esperada

tempo O(n × k), espaço extra O(k)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.