Pythonで顧客の平均待ち時間を求めるプログラムの実装方法

レストランのキッチンをシミュレートする古典的なアルゴリズム問題を考えてみましょう。配列 customers があり、その各要素 customers[i] は [arrival_i, time_i] というペアを表しています。arrival_i は i 番目の顧客の到着時刻(昇順にソート済み)、time_i はその顧客の注文を準備するために必要な時間です。

顧客が到着すると注文を行いますが、その注文の調理はコックが手空きになったときにのみ開始されます。コックは同時に複数の顧客の料理を作ることができず、必ず注文された順番どおりに調理を行います。このとき、全顧客の平均待ち時間を求めるのがこの問題の目的です。

具体例で理解する

たとえば、入力が customers = [[7,2],[8,4],[10,3],[20,1]] の場合、出力は 3.5 になります。それぞれの顧客の流れを順番に見てみましょう。

• 1人目の顧客:時刻 7 に到着。コックはすぐに注文を受けて時刻 7 に調理を開始し、時刻 9 に完了します。待ち時間は 9 − 7 = 2。

• 2人目の顧客:時刻 8 に到着。コックは時刻 9 に調理を開始し、時刻 13 に完了します。待ち時間は 13 − 8 = 5。

• 3人目の顧客:時刻 10 に到着。コックは時刻 13 に調理を開始し、時刻 16 に完了します。待ち時間は 16 − 10 = 6。

• 4人目の顧客:時刻 20 に到着。コックは手空きなので、すぐに時刻 20 に調理を開始し、時刻 21 に完了します。待ち時間は 21 − 20 = 1。

したがって、平均待ち時間は (2 + 5 + 6 + 1) ÷ 4 = 3.5 となります。

解法のアプローチ

この問題は、コックの状態を時系列に沿ってシミュレートすることで解けます。以下の手順に従います。

• 各顧客の待ち時間を格納するための新しいリスト arr を用意する
• コックの空き時刻を表す変数 time を 0 で初期化する
• customers の各ペア (i, j) について以下を繰り返す:
  • i > time の場合(顧客の到着時にコックが手空き):
    • time := i + j
  • それ以外の場合(コックが前の注文を処理中):
    • time := time + j
• リスト arr の末尾に (time − i)、つまりその顧客の待ち時間を追加する
• arr 内の全要素の平均値を返す

アルゴリズムのポイント

変数 time は常に「コックが次の注文に取りかかれる時刻」を追跡しています。顧客が到着した時点でコックが手空きなら調理は到着時刻から始まり、そうでなければ前の注文の完了時刻から始まります。各顧客の待ち時間は「注文完了時刻 − 到着時刻」で計算できるため、これをすべて合計して人数で割れば平均待ち時間が求められます。計算量は O(n) と非常に効率的です。

実装例

以下がPythonでの実装例です。

def solve(customers):
    arr = []

    time = 0

    for i , j in customers:
        if(i > time):
            time = i + j
        else:
            time += j
        arr.append(time - i)

    return sum(arr) / len(arr)

customers = [[7,2],[8,4],[10,3],[20,1]]
print(solve(customers))

入力

[[7,2],[8,4],[10,3],[20,1]]

出力

3.5