平均等待时间

标签: 数组 模拟

难度: Medium

有一个餐厅，只有一位厨师。你有一个顾客数组 customers ，其中 customers[i] = [arrivali, timei] ：

  • arrivali 是第 i 位顾客到达的时间，到达时间按 非递减 顺序排列。
  • timei 是给第 i 位顾客做菜需要的时间。

当一位顾客到达时，他将他的订单给厨师，厨师一旦空闲的时候就开始做这位顾客的菜。每位顾客会一直等待到厨师完成他的订单。厨师同时只能做一个人的订单。厨师会严格按照 订单给他的顺序 做菜。

请你返回所有顾客需要等待的 平均 时间。与标准答案误差在 10-5 范围以内，都视为正确结果。

 

示例 1：

输入：customers = [[1,2],[2,5],[4,3]]
输出：5.00000
解释：
1) 第一位顾客在时刻 1 到达，厨师拿到他的订单并在时刻 1 立马开始做菜，并在时刻 3 完成，第一位顾客等待时间为 3 - 1 = 2 。
2) 第二位顾客在时刻 2 到达，厨师在时刻 3 开始为他做菜，并在时刻 8 完成，第二位顾客等待时间为 8 - 2 = 6 。
3) 第三位顾客在时刻 4 到达，厨师在时刻 8 开始为他做菜，并在时刻 11 完成，第三位顾客等待时间为 11 - 4 = 7 。
平均等待时间为 (2 + 6 + 7) / 3 = 5 。

示例 2：

输入：customers = [[5,2],[5,4],[10,3],[20,1]]
输出：3.25000
解释：
1) 第一位顾客在时刻 5 到达，厨师拿到他的订单并在时刻 5 立马开始做菜，并在时刻 7 完成，第一位顾客等待时间为 7 - 5 = 2 。
2) 第二位顾客在时刻 5 到达，厨师在时刻 7 开始为他做菜，并在时刻 11 完成，第二位顾客等待时间为 11 - 5 = 6 。
3) 第三位顾客在时刻 10 到达，厨师在时刻 11 开始为他做菜，并在时刻 14 完成，第三位顾客等待时间为 14 - 10 = 4 。
4) 第四位顾客在时刻 20 到达，厨师拿到他的订单并在时刻 20 立马开始做菜，并在时刻 21 完成，第四位顾客等待时间为 21 - 20 = 1 。
平均等待时间为 (2 + 6 + 4 + 1) / 4 = 3.25 。

 

提示：

  • 1 <= customers.length <= 105
  • 1 <= arrivali, timei <= 104
  • arrivali <= arrivali+1

Submission

运行时间: 59 ms

内存: 46.7 MB

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        k = customers[0][0]+customers[0][1]
        m = customers[0][1]
        ans = [m]       
        for x, y in customers[1:]:
            if k >= x:
                k += y
            if k < x:
                k = x + y
            ans.append(k-x)
        return sum(ans)/len(customers)

Explain

此题解通过维护一个当前时间变量 k 来记录厨师何时完成当前顾客的菜。遍历每个顾客，比较厨师的空闲时间 k 与顾客到达时间 x。如果厨师在顾客到达前就空闲了，厨师将在顾客到达时立即开始制作，否则厨师会在处理完上一顾客后立即开始制作。每次厨师完成一个顾客的菜，更新时间 k，并计算该顾客的等待时间，存入 ans 列表。最后，计算所有顾客等待时间的平均值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        # 初始化厨师完成时间为第一个顾客到达加上烹饪时间
        k = customers[0][0] + customers[0][1]
        # 第一个顾客的等待时间等于他的烹饪时间
        m = customers[0][1]
        ans = [m]  # 存储所有顾客的等待时间
        for x, y in customers[1:]:
            if k >= x:
                k += y  # 厨师在顾客到达时已经空闲，直接烹饪
            if k < x:
                k = x + y  # 厨师在顾客到达后才空闲，等到顾客到达再开始烹饪
            ans.append(k - x)  # 计算等待时间并添加到列表
        return sum(ans) / len(customers)  # 计算平均等待时间

Explore

题解的代码没有直接处理顾客数组为空的情况，这可能导致在初始化k的时候出现索引错误，因为customers[0][0]和customers[0][1]会在customers为空时引发异常。然而，对于只有一个顾客的情况，题解是有效的，因为它初始化k和m，然后直接返回m作为平均等待时间。为了使代码更健壮，应该在代码开始时加入对customers是否为空的检查，如果为空，则应该返回0或其他合适的值表示没有等待时间。