🔗 🟡 1701. Average Waiting Time 1436

tags: `Biweekly Contest 42` `陣列(Array)` `模擬(Simulation)` `FCFS`

題意

有一家只有一位廚師的餐廳，給定一個二維整數陣列 $customers$ ，其中 $customers[i] = [arrival_i, time_i]$ ：

$arrival_i$ 表示第 $i$ 個顧客到達的時間，並且陣列已按照到達時間的 非遞減 順序排列。
$time_i$ 表示準備第 $i$ 個顧客餐點所需的時間。

當一位顧客到達時，他會將他的訂單交給廚師，廚師一旦空閒就會開始為這位顧客準備餐點。每位顧客會一直等待到廚師完成他的訂單。廚師同時只能為一位顧客準備餐點。廚師會嚴格按照 訂單給他的順序 來準備餐點。

返回所有顧客需要等待的平均時間。與標準答案誤差在 $10^{-5}$ 範圍以內，都視為正確結果。

思路：FCFS(First-Come, First-Served)

根據題意，這位廚師是按照作業系統中的 FCFS(First-Come, First-Served) 原則來為顧客準備餐點。換句話說，後到達的顧客必須等待前面的顧客先完成訂單。

因此可以維護前一個顧客的完成時間 $cur$ ，也就是可以開始準備下一個顧客訂單的時間。對於每個顧客而言：

如果當前時間 $cur$ 小於或等於該顧客的到達時間 $arrival_i$ ，表示廚師在該名顧客到達時是空閒的，可以立即開始準備。此時 $cur^{\prime}$ 會更新為 $arrival_i + time_i$ 。
如果當前時間 $cur$ 大於該顧客的到達時間 $arrival_i$ ，表示該顧客必須等待到 $cur$ 時間才能開始準備。此時 $cur^{\prime}$ 會更新為 $cur + time_i$ 。

因此每名顧客的等待時間為 $cur^{\prime} - arrival_i$ ，將所有顧客的等待時間相加，最後除以顧客總數即可得到平均等待時間。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，由於已經按照到達時間排序，因此只需要遍歷所有顧客一次。
空間複雜度： $\mathcal{O}(1)$ ，只使用了常數級別的額外空間。

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        n = len(customers)
        tot = 0 # total waiting time
        cur = 0 # current time
        for a, t in customers:
            cur = max(cur, a) + t
            tot += cur - a
        return tot / n

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        int n = customers.size();
        double tot = 0;
        int cur = 0;
        for (auto& c : customers) {
            cur = max(cur, c[0]) + c[1];
            tot += cur - c[0];
        }
        return tot / n;
    }
};