Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Warteschlange in der Bank simulieren

Simuliere Kunden, die in einer gemeinsamen Schlange auf mehrere Bankschalter warten, und gib die Wartezeiten aus.

Das lernst du

  • Kunden nach dem Prinzip "wer zuerst kommt, wird zuerst bedient" abfertigen
  • Mitführen, wann jeder Schalter frei wird
  • Kennzahlen aus einer Simulation sammeln

Problem

Eine Bank hat tellers Schalter und eine einzige Warteschlange. Kunde i kommt in Minute arrivals[i] an und braucht service[i] Minuten am Schalter. Die Kunden werden streng in der Reihenfolge ihrer Ankunft bedient (der Reihenfolge der Listen). Ist ein Kunde vorne in der Schlange angekommen, geht er zu dem Schalter, der am frühesten frei wird (bei Gleichstand zu dem mit der kleinsten Nummer), und beginnt zum späteren der beiden Zeitpunkte: seiner Ankunft oder dem Freiwerden des Schalters. Jeder Schalter ist ab Minute 0 frei.

Die Wartezeit eines Kunden ist seine Startzeit minus seine Ankunftszeit.

Implementiere bank_queue_simulation(arrivals, service, tellers).

Eingabe

arrivals: Die Ankunftsminuten, aufsteigend sortiert (gleiche Werte sind erlaubt).

service: Die Bedienzeit jedes Kunden in Minuten, in derselben Reihenfolge.

tellers: Die Anzahl der Schalter.

Ausgabe

Gib [total_wait, longest_wait, last_finish] zurück: die Summe aller Wartezeiten, die längste einzelne Wartezeit und die Minute, in der der letzte Kunde fertig ist. Ohne Kunden gib [0, 0, 0] zurück.

Einschränkungen

0 ≤ Anzahl der Kunden ≤ 2000

0 ≤ Ankunft ≤ 100 000

1 ≤ Bedienzeit ≤ 1000

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

Kunde 1 und 2 kommen sofort dran (bei 0 und 1). Schalter 2 wird bei 4 frei, also wartet Kunde 3 zwei Minuten; Schalter 1 wird bei 5 frei, also wartet Kunde 4 zwei Minuten. Fertig ist der Letzte bei 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

Mit einem Schalter betragen die Wartezeiten 0, 4 und 8, und der letzte Kunde ist bei 12 fertig: [12, 8, 12].

So gehst du vor

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

Hinweis 1

Führe ein Array mit der Minute, in der jeder Schalter frei wird.

Hinweis 2

Wähle für jeden Kunden die kleinste Freiwerdezeit (bei Gleichstand den kleinsten Index).

Hinweis 3

Die Startzeit ist der spätere Zeitpunkt aus Ankunft und Freiwerdezeit; die Wartezeit ist Start minus Ankunft.

Erwartete Komplexität

Zeit O(n × k), zusätzlicher Speicher O(k)

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.