開店と同時に客が一斉に来たら?
近所のカフェ「コードビーン」が開いた瞬間、客5人が押し寄せて同時に注文しました。バリスタは一度に一杯ずつしか作れず、各ドリンクの調理時間はバラバラです。
調理時間(分): [3, 1, 4, 1, 5]
客は自分のドリンクができるまで待ちます。では誰のドリンクから作れば、全員の待ち時間の合計が最も小さくなるでしょう?
カギは「前の注文ほど何度も加算される」
先に作る注文が遅いと、その後ろで待つ全員が一緒にその分だけ長く待ちます。つまり前に置いた注文の調理時間は、一度ではなく何度も総待ち時間に加算されるのです。
もう少し正確に — 調理時間 c の注文を前から k 番目に置くと、その c は自分の客+後ろに残った客全員が耐えるので、合計に (N - k) 回加算されます。
だから結論は自然です。繰り返しが最も多い先頭には、最も短い注文を置こう。 短いドリンクを先に出せば、後ろの客の累積待ちを最小に抑えられます。
なぜ「短い順」が常に正しい? (交換論法)
直感は分かるけれど、*本当に常に*最適でしょうか? 隣り合う2つの注文だけを取り出してみます。前に a、すぐ後ろに b があるとき、この2つの順を入れ替えても他の客の待ちは全く変わりません。 変わるのはこの2注文自身の待ちだけです。
- •
aを先に:a + (a + b) - •
bを先に:b + (a + b)
差はちょうど a - b。つまり a > b なら b を前へ送るのが必ず得です。これが*すべての*隣接ペアで成り立つので、もう入れ替えで得できない状態 = 調理時間の昇順が最適、という結論に至ります。
まとめると解法はこれだけに縮みます。
1. 調理時間を昇順にソートする
2. 前から足して累積調理時間(= 各客の完了時刻) を求める
3. 完了時刻を全部足せば、それが最小総待ち時間
[3,1,4,1,5] をソートすると [1,1,3,4,5]、完了時刻は 1, 2, 5, 9, 14 — 合計は31分です。(入力順のまま作ると38分で損です。)
目で見ると「なぜ最小か」が刺さる
「(N - k) 回加算される」と聞いてもピンと来ないかもしれません。でもバーを時間軸に並べて見れば話は別です。短いバーを前に置くほど、後ろのバーの開始点が左へ寄り、完了時刻の合計が縮むのが一目で分かります。
- •注文を調理時間のバーとして描き
- •短い順にソートして
- •1つずつ処理しながら累積待ち時間が積み上がる過程を
ステップごとのアニメーションで追うと、「*だから*短い順なのか」が一瞬で腑に落ちます。
このパターン(ソート後に累積和の貪欲法)は「会議室割り当て」「ジョブスケジューリング」「最小平均待ち時間」など無数の姿でコーディングテストに登場します。一度原理を目で覚えれば、どんな変形が出ても揺らぎません。