1701. 平均等待时间

题目描述

有一个餐厅，只有一位厨师。你有一个顾客数组 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

解法

方法一：模拟

我们用变量 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)$。

Python3JavaC++GoTypeScriptRustJavaScript

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)

class Solution {
    public double averageWaitingTime(int[][] customers) {
        double tot = 0;
        int t = 0;
        for (var e : customers) {
            int a = e[0], b = e[1];
            t = Math.max(t, a) + b;
            tot += t - a;
        }
        return tot / customers.length;
    }
}

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

func averageWaitingTime(customers [][]int) float64 {
    tot, t := 0, 0
    for _, e := range customers {
        a, b := e[0], e[1]
        t = max(t, a) + b
        tot += t - a
    }
    return float64(tot) / float64(len(customers))
}

function averageWaitingTime(customers: number[][]): number {
    let [tot, t] = [0, 0];
    for (const [a, b] of customers) {
        t = Math.max(t, a) + b;
        tot += t - a;
    }
    return tot / customers.length;
}

impl Solution {
    pub fn average_waiting_time(customers: Vec<Vec<i32>>) -> f64 {
        let mut tot = 0.0;
        let mut t = 0;

        for e in customers.iter() {
            let a = e[0];
            let b = e[1];
            t = t.max(a) + b;
            tot += (t - a) as f64;
        }

        tot / customers.len() as f64
    }
}

function averageWaitingTime(customers) {
    let [tot, t] = [0, 0];
    for (const [a, b] of customers) {
        t = Math.max(t, a) + b;
        tot += t - a;
    }
    return tot / customers.length;
}

1701. 平均等待时间

题目描述

解法

方法一：模拟

评论