問題
ある銀行には 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
例
入力:
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] です。
入力:
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用に調整されています。上記の説明と制約に従ってください。