情境模擬: 平均等待時間 Average Waiting Time_Leetcode #1707

iorni.com null on Unsplash

題目敘述 Average Waiting Time

給定一個陣列，分別代表每位顧客的抵達時間和廚師準備時間。

請問平均的等待時間是多少?

等待時間定義為 客人開始真正用餐的時間 - 客人抵達的時間。

測試範例

Example 1:

Input: customers = [[1,2],[2,5],[4,3]]
Output: 5.00000
Explanation:
1) The first customer arrives at time 1, the chef takes his order and starts preparing it immediately at time 1, and finishes at time 3, so the waiting time of the first customer is 3 - 1 = 2.
2) The second customer arrives at time 2, the chef takes his order and starts preparing it at time 3, and finishes at time 8, so the waiting time of the second customer is 8 - 2 = 6.
3) The third customer arrives at time 4, the chef takes his order and starts preparing it at time 8, and finishes at time 11, so the waiting time of the third customer is 11 - 4 = 7.
So the average waiting time = (2 + 6 + 7) / 3 = 5.

Example 2:

Input: customers = [[5,2],[5,4],[10,3],[20,1]]
Output: 3.25000
Explanation:
1) The first customer arrives at time 5, the chef takes his order and starts preparing it immediately at time 5, and finishes at time 7, so the waiting time of the first customer is 7 - 5 = 2.
2) The second customer arrives at time 5, the chef takes his order and starts preparing it at time 7, and finishes at time 11, so the waiting time of the second customer is 11 - 5 = 6.
3) The third customer arrives at time 10, the chef takes his order and starts preparing it at time 11, and finishes at time 14, so the waiting time of the third customer is 14 - 10 = 4.
4) The fourth customer arrives at time 20, the chef takes his order and starts preparing it immediately at time 20, and finishes at time 21, so the waiting time of the fourth customer is 21 - 20 = 1.
So the average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25.

約束條件

Constraints:

• 1 <= customers.length <= 10^5

輸入陣列長度介於1~十萬之間

• 1 <= arrivali, timei <= 10^4

抵達時間和準備時間都介於1~一萬之間。

• arrivali <= arrivali+1

抵達時間一定是遞增序列

演算法 計算廚師的出餐時間

等待時間

=客人開始真正用餐的時間 - 客人抵達的時間。

=廚師出餐的時間 - 客人抵達的時間。

根據題意，
根據每個客人的抵達時間和廚師出餐時間去計算等待時間，最後再取平均即可。

要留意的是，廚師只有在出完前一位客人的餐點之後，才會給下一個客人出餐。

程式碼 計算廚師的出餐時間

class Solution:
    def averageWaitingTime(self, customers: list[list[int]]) -> float:
        n = len(customers)

        time_waiting = 0
        finished_prev = -math.inf

        for customer_arrive, customer_prepare in customers:

            arrive = customer_arrive

            # chef starts cook this as soon as he finished last dish or customer arrived
            start_cook = max(arrive, finished_prev)
            end_time = start_cook + customer_prepare

            # accumulate time of waiting
            time_waiting += end_time - arrive

            # update previous finished time
            finished_prev = end_time
            
        return time_waiting / n

複雜度分析

時間複雜度:O(n)

依序掃描每一位客人的抵達時間和廚師準備時間。

空間複雜度:O(1)

所用到的都是固定尺寸的臨時變數，所需空間為O(1)常數級別。

Reference:

[1] Average Waiting Time - LeetCode