すべてのチャレンジ
中級 0件解決済み 正答率0%

銀行の待ち行列シミュレーション

複数の窓口に1列で並ぶ客をシミュレートし、待ち時間を報告します。

このチャレンジで学べること

  • 先着順で客に対応する
  • 各窓口が空く時刻を記録する
  • シミュレーションから集計値を求める

問題

原文(英語)を表示

ある銀行には tellers 個の窓口と、1本の待ち行列があります。客 i は arrivals[i] 分に到着し、窓口で service[i] 分かかります。客は到着順(リストの順)に厳密に対応されます。列の先頭に来た客は、いちばん早く空く窓口(同時なら番号の小さい窓口)へ行き、自分の到着時刻とその窓口が空く時刻の遅い方から対応が始まります。どの窓口も0分から空いています。

客の待ち時間は、開始時刻から到着時刻を引いたものです。

bank_queue_simulation(arrivals, service, tellers) を実装してください。

入力

arrivals: 到着時刻(分)。小さい順(同じ値を含む)に並んでいます。

service: 各客の対応時間(分)。同じ順に並んでいます。

tellers: 窓口の数。

出力

全員の待ち時間の合計、1人あたりの最長の待ち時間、最後の客の対応が終わる時刻(分)を [total_wait, longest_wait, last_finish] として返してください。客がいなければ [0, 0, 0] を返します。

制約

0 ≤ 客の数 ≤ 2,000

0 ≤ 到着時刻 ≤ 100,000

1 ≤ 対応時間 ≤ 1,000

1 ≤ tellers ≤ 20

例

例 1
入力:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

期待される出力:
expected = [4, 2, 8]
入力:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;

期待される出力:
std::vector<long long> expected = {4, 2, 8};
入力:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;

期待される出力:
long[] expected = new long[] {4, 2, 8};

解説

客1と客2はすぐに始まります(0分と1分)。窓口2は4分に空くので客3は2分待ち、窓口1は5分に空くので客4は2分待ちます。最後の終了時刻は max(8, 7) = 8 なので [4, 2, 8] です。

例 2
入力:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

期待される出力:
expected = [12, 8, 12]
入力:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;

期待される出力:
std::vector<long long> expected = {12, 8, 12};
入力:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;

期待される出力:
long[] expected = new long[] {12, 8, 12};

解説

窓口が1つなら待ち時間は0分、4分、8分で、最後の客は12分に終わるので [12, 8, 12] です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

各窓口が空く時刻を配列で持っておきましょう。

ヒント 2

各客について、空く時刻が最も早い窓口を選びます(同時なら添字の小さい方)。

ヒント 3

開始時刻は到着時刻とその空く時刻の遅い方で、待ち時間は開始時刻から到着時刻を引いたものです。

目安の計算量

時間 O(n × k)、追加メモリ O(k)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。