What is the main pattern to recognize in Average Waiting Time?

The problem follows an Array plus Simulation pattern, iterating through customer arrivals while maintaining sequential chef processing.

How do I handle customers arriving while the chef is busy?

Use max(arrivalTime, chefAvailableTime) to determine when the chef starts each order, ensuring correct waiting time calculation.

Is floating point precision important for the average?

Yes, ensure results are accurate within 10^-5 by using appropriate float or double division when computing averages.

Can this solution handle large arrays efficiently?

Yes, the algorithm runs in O(n) time and O(1) space, suitable for arrays up to 10^5 elements.

What common mistakes should I avoid in this simulation?

Avoid miscalculating start times, skipping the max(arrival, chefAvailable) logic, or using integer division when computing the average.

#1701

Medium

auto_awesome数组·模拟

LeetCode 题解工作台

平均等待时间

有一个餐厅，只有一位厨师。你有一个顾客数组 customers ，其中 customers[i] = [arrival i , time i ] ： arrival i 是第 i 位顾客到达的时间，到达时间按非递减顺序排列。 time i 是给第 i 位顾客做菜需要的时间。当一位顾客到达时，他…

数组模拟

题目描述

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

arrival_i 是第 i 位顾客到达的时间，到达时间按 非递减 顺序排列。
time_i 是给第 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 <= 10⁵
1 <= arrival_i, time_i <= 10⁴
arrival_i<= arrival_i+1

lightbulb

解题思路

方法一：模拟

我们用变量 tot 记录顾客的总等待时间，用变量 t 记录做完每个顾客的订单的时间，初始值均为 $0$ 。

遍历顾客数组 customers，对于每个顾客：

如果当前时间 t 小于等于顾客的到达时间 customers[i][0]，说明厨师没有在做菜，那么厨师可以立即开始做菜，做完这道菜的时间为 $t = customers[i][0] + customers[i][1]$ ，顾客的等待时间为 customers[i][1]。

否则，说明厨师正在做菜，那么顾客需要等待厨师做完此前的菜，才能开始做自己的菜，做完这道菜的时间为 $t = t + customers[i][1]$ ，顾客的等待时间为 $t - customers[i][0]$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为顾客数组 customers 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        tot = t = 0
        for a, b in customers:
            t = max(t, a) + b
            tot += t - a
        return tot / len(customers)

speed

复杂度分析

指标	值
时间	complexity is O(n) because we iterate through the customer array once, computing waiting times. Space complexity is O(1) since only counters and time trackers are maintained without extra arrays.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Watch for handling customers arriving while the chef is still busy.
question_mark
Ensure floating point precision is accurate for the average calculation.
question_mark
Check if the simulation correctly updates chef availability after each order.

warning

常见陷阱

外企场景

error
Starting the chef's time from zero without accounting for initial customer arrival.
error
Incorrectly calculating waiting time by not using max(arrival, chefAvailable).
error
Accumulating waiting times as integers without converting to float for average.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Calculate maximum waiting time instead of average to identify peak delays.
arrow_right_alt
Simulate multiple chefs processing orders concurrently while maintaining order sequence per chef.
arrow_right_alt
Handle dynamic arrivals where customers may cancel or add orders during simulation.

help

常见问题

外企场景

继续练习

#1700 无法吃午餐的学生数量 #1706 球会落何处 #1646 获取生成数组中的最大值