Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Bank Queue Simulation

Simulate customers waiting in one line for several bank tellers and report the waiting times.

Das lernst du

  • Serve customers in first-come, first-served order
  • Track when each server becomes free
  • Collect summary statistics from a simulation

Problem

Übersetzung anzeigen

A bank has tellers tellers and a single waiting line. Customer i arrives at minute arrivals[i] and needs service[i] minutes at a teller. Customers are served strictly in arrival order (the order of the lists). When a customer reaches the front of the line, they go to the teller who becomes free the earliest (the lowest numbered one on a tie), and start at the later of their arrival time and that teller's free time. A teller is free from minute 0.

A customer's wait is their start time minus their arrival time.

Implement bank_queue_simulation(arrivals, service, tellers).

Input

arrivals: Arrival minutes in non-decreasing order.

service: Service minutes for each customer, in the same order.

tellers: The number of tellers.

Output

Return [total_wait, longest_wait, last_finish]: the sum of all waits, the largest single wait, and the minute the last customer finishes. With no customers return [0, 0, 0].

Einschränkungen

0 ≤ number of customers ≤ 2,000

0 ≤ arrival ≤ 100,000

1 ≤ service ≤ 1,000

1 ≤ tellers ≤ 20

Beispiele

Beispiel 1
Eingabe:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

Erwartete Ausgabe:
expected = [4, 2, 8]
Eingabe:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;

Erwartete Ausgabe:
std::vector<long long> expected = {4, 2, 8};
Eingabe:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;

Erwartete Ausgabe:
long[] expected = new long[] {4, 2, 8};

Erläuterung

Customers 1 and 2 start at once (0 and 1). Teller 2 frees at 4, so customer 3 waits 2; teller 1 frees at 5, so customer 4 waits 2. Last finish is max(8, 7) = 8: [4, 2, 8].

Beispiel 2
Eingabe:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

Erwartete Ausgabe:
expected = [12, 8, 12]
Eingabe:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;

Erwartete Ausgabe:
std::vector<long long> expected = {12, 8, 12};
Eingabe:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;

Erwartete Ausgabe:
long[] expected = new long[] {12, 8, 12};

Erläuterung

With one teller the waits are 0, 4 and 8, and the last customer finishes at 12: [12, 8, 12].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Keep an array with the minute each teller becomes free.

Hinweis 2

For each customer pick the smallest free time (lowest index on a tie).

Hinweis 3

Start time is the later of arrival and that free time; the wait is start minus arrival.

Erwartete Komplexität

O(n × k) time, O(k) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.