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 <= 10^5
  • 1 <= arrivali, timei <= 10^4
  • arrivali <= arrivali+1

解题思路

这道题目考查的是模拟问题，需要模拟厨师处理订单的过程。

核心思路：

我们需要跟踪厨师当前完成订单的时间，对于每个顾客，计算他们的等待时间。

算法步骤：

  1. 维护一个变量 currentTime 表示厨师完成当前所有订单的时间
  2. 遍历每个顾客：
    • 如果厨师在顾客到达前就空闲了（currentTime <= arrival），那么厨师可以立即开始准备，开始时间就是顾客到达时间
    • 如果厨师仍在忙碌（currentTime > arrival），那么顾客需要等待到厨师完成前面的订单
    • 计算完成时间：开始时间 + 准备时间
    • 等待时间 = 完成时间 - 到达时间
  3. 累计所有等待时间，最后计算平均值

关键点：

  • 厨师的开始时间是 max(currentTime, arrival)
  • 完成时间是开始时间加上准备时间
  • 等待时间是完成时间减去到达时间

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)，是最优解法。

代码实现

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        long long totalWaitTime = 0;
        int currentTime = 0;
        
        for (const auto& customer : customers) {
            int arrival = customer[0];
            int cookTime = customer[1];
            
            // 厨师开始准备的时间
            int startTime = max(currentTime, arrival);
            // 完成时间
            int finishTime = startTime + cookTime;
            // 等待时间
            int waitTime = finishTime - arrival;
            
            totalWaitTime += waitTime;
            currentTime = finishTime;
        }
        
        return (double)totalWaitTime / customers.size();
    }
};

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        total_wait_time = 0
        current_time = 0
        
        for arrival, cook_time in customers:
            # 厨师开始准备的时间
            start_time = max(current_time, arrival)
            # 完成时间
            finish_time = start_time + cook_time
            # 等待时间
            wait_time = finish_time - arrival
            
            total_wait_time += wait_time
            current_time = finish_time
        
        return total_wait_time / len(customers)

public class Solution {
    public double AverageWaitingTime(int[][] customers) {
        long totalWaitTime = 0;
        int currentTime = 0;
        
        foreach (var customer in customers) {
            int arrival = customer[0];
            int cookTime = customer[1];
            
            // 厨师开始准备的时间
            int startTime = Math.Max(currentTime, arrival);
            // 完成时间
            int finishTime = startTime + cookTime;
            // 等待时间
            int waitTime = finishTime - arrival;
            
            totalWaitTime += waitTime;
            currentTime = finishTime;
        }
        
        return (double)totalWaitTime / customers.Length;
    }
}

var averageWaitingTime = function(customers) {
    let totalWaitTime = 0;
    let currentTime = 0;
    
    for (const [arrival, cookTime] of customers) {
        // 厨师开始准备的时间
        const startTime = Math.max(currentTime, arrival);
        // 完成时间
        const finishTime = startTime + cookTime;
        // 等待时间
        const waitTime = finishTime - arrival;
        
        totalWaitTime += waitTime;
        currentTime = finishTime;
    }
    
    return totalWaitTime / customers.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历所有顾客一次
空间复杂度O(1)只使用常数额外空间

相关题目