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