Tous les défis
Moyen 0 résolus 0 % de réussite

Simulation de file d'attente à la banque

Simulez des clients qui attendent dans une file unique devant plusieurs guichets et donnez les temps d'attente.

Ce que vous allez apprendre

  • Servir les clients selon la règle premier arrivé, premier servi
  • Suivre le moment où chaque guichet se libère
  • Calculer des statistiques récapitulatives à partir d'une simulation

Problème

Une banque dispose de tellers guichetiers et d'une seule file d'attente. Le client i arrive à la minute arrivals[i] et a besoin de service[i] minutes au guichet. Les clients sont servis strictement dans leur ordre d'arrivée (l'ordre des listes). Quand un client arrive en tête de file, il va au guichetier qui se libère le plus tôt (celui de plus petit numéro en cas d'égalité), et il commence au plus tard entre son heure d'arrivée et l'heure où ce guichetier se libère. Tous les guichetiers sont libres dès la minute 0.

L'attente d'un client est son heure de début moins son heure d'arrivée.

Implémentez bank_queue_simulation(arrivals, service, tellers).

Entrée

arrivals : les minutes d'arrivée, dans l'ordre croissant au sens large.

service : la durée de service de chaque client en minutes, dans le même ordre.

tellers : le nombre de guichetiers.

Sortie

Renvoyez [total_wait, longest_wait, last_finish] : la somme de toutes les attentes, la plus longue attente individuelle et la minute à laquelle le dernier client termine. Sans aucun client, renvoyez [0, 0, 0].

Contraintes

0 ≤ nombre de clients ≤ 2 000

0 ≤ arrivée ≤ 100 000

1 ≤ service ≤ 1 000

1 ≤ tellers ≤ 20

Exemples

Exemple 1
Entrée :
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

Sortie attendue :
expected = [4, 2, 8]
Entrée :
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;

Sortie attendue :
std::vector<long long> expected = {4, 2, 8};
Entrée :
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;

Sortie attendue :
long[] expected = new long[] {4, 2, 8};

Explication

Les clients 1 et 2 commencent dès leur arrivée (0 et 1). Le guichetier 2 se libère à 4, donc le client 3 attend 2 ; le guichetier 1 se libère à 5, donc le client 4 attend 2. La dernière fin est max(8, 7) = 8 : [4, 2, 8].

Exemple 2
Entrée :
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

Sortie attendue :
expected = [12, 8, 12]
Entrée :
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;

Sortie attendue :
std::vector<long long> expected = {12, 8, 12};
Entrée :
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;

Sortie attendue :
long[] expected = new long[] {12, 8, 12};

Explication

Avec un seul guichetier, les attentes sont 0, 4 et 8, et le dernier client termine à 12 : [12, 8, 12].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Gardez un tableau contenant la minute à laquelle chaque guichetier se libère.

Indice 2

Pour chaque client, choisissez le plus petit temps de libération (le plus petit indice en cas d'égalité).

Indice 3

L'heure de début est le maximum entre l'arrivée et ce temps de libération ; l'attente est le début moins l'arrivée.

Complexité attendue

temps O(n × k), espace supplémentaire O(k)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.