Leetcode 1701. Average Waiting Time

Problem Description

In this problem, we have a restaurant with a single chef and an array of customers, where each customer has an arrival time and the time needed to prepare his order. The chef starts preparing a customer's order when he is idle. The customers wait till the chef finishes preparing their order. The chef prepares food for customers in the order they were given in the input.

The task is to return the average waiting time of all customers. Solutions within 10^-5 from the actual answer are considered accepted.

For example, consider the following customers array:

1customers = [[1, 2], [2, 5], [4, 3]]

We can calculate the average waiting time as follows:

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.

Approach

The approach for this problem is to iterate through the customers array and keep track of the current time (curr) at which the chef is preparing each customer's order. The waiting time for each customer is calculated as the difference between the current time and their arrival time. Finally, the total waiting time is divided by the number of customers to get the average waiting time.

Here's an example:

Let's use the same example as before:

1customers = [[1, 2], [2, 5], [4, 3]]

1. The first customer arrives at time 1, and the chef starts preparing the order immediately at time 1 (curr = 1). So, curr = max(curr, arrival[0]) + time[0] = max(1, 1) + 2 = 3. The waiting time for this customer is 3 - 1 = 2.
2. The second customer arrives at time 2, and the chef starts preparing the order at time 3 (curr = 3). So, curr = max(curr, arrival[1]) + time[1] = max(3, 2) + 5 = 8. The waiting time for this customer is 8 - 2 = 6.
3. The third customer arrives at time 4, and the chef starts preparing the order at time 8 (curr = 8). So, curr = max(curr, arrival[2]) + time[2] = max(8, 4) + 3 = 11. The waiting time for this customer is 11 - 4 = 7.

Finally, the average waiting time is (2 + 6 + 7) / 3 = 5.

C++ Solution

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6 public:
7  double averageWaitingTime(vector<vector<int>>& customers) {
8    double wait = 0;
9    double curr = 0;
10
11    // Iterate over the customers array
12    for (const vector<int>& c : customers) {
13      // Update the current time at which the chef starts preparing each customer's order
14      curr = max(curr, 1.0 * c[0]) + c[1];
15      // Calculate the waiting time for this customer and add it to the total waiting time
16      wait += curr - c[0];
17    }
18
19    // Return the average waiting time by dividing the total waiting time by the number of customers
20    return 1.0 * wait / customers.size();
21  }
22};

Note that in the solution, we first initialize the wait and curr variables to store the total waiting time and the current time at which the chef starts preparing the order. Then, we iterate through the customers array, update the current time and calculate the waiting time for each customer. Finally, we return the average waiting time by dividing the total waiting time by the number of customers.## Python Solution

1class Solution:
2    def averageWaitingTime(self, customers: List[List[int]]) -> float:
3        wait = 0
4        curr = 0
5
6        # Iterate over the customers array
7        for arrival, time in customers:
8            # Update the current time at which the chef starts preparing each customer's order
9            curr = max(curr, arrival) + time
10            # Calculate the waiting time for this customer and add it to the total waiting time
11            wait += curr - arrival
12
13        # Return the average waiting time by dividing the total waiting time by the number of customers
14        return wait / len(customers)

JavaScript Solution

1class Solution {
2    averageWaitingTime(customers) {
3        let wait = 0;
4        let curr = 0;
5
6        // Iterate over the customers array
7        for (const [arrival, time] of customers) {
8            // Update the current time at which the chef starts preparing each customer's order
9            curr = Math.max(curr, arrival) + time;
10            // Calculate the waiting time for this customer and add it to the total waiting time
11            wait += curr - arrival;
12        }
13
14        // Return the average waiting time by dividing the total waiting time by the number of customers
15        return wait / customers.length;
16    }
17}

Java Solution

1class Solution {
2    public double averageWaitingTime(int[][] customers) {
3        double wait = 0;
4        double curr = 0;
5
6        // Iterate over the customers array
7        for (int[] c : customers) {
8            // Update the current time at which the chef starts preparing each customer's order
9            curr = Math.max(curr, 1.0 * c[0]) + c[1];
10            // Calculate the waiting time for this customer and add it to the total waiting time
11            wait += curr - c[0];
12        }
13
14        // Return the average waiting time by dividing the total waiting time by the number of customers
15        return 1.0 * wait / customers.length;
16    }
17}

In all the solutions above, the approach is the same as explained in the Approach section. We first initialize the wait and curr variables to store the total waiting time and the current time at which the chef starts preparing the order. Then, we iterate through the customers array, update the current time, and calculate the waiting time for each customer. Finally, we return the average waiting time by dividing the total waiting time by the number of customers.