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:
- 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.
- 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.
- 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]]
- 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.
- 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.
- 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.