1701. Average Waiting Time

Problem Description: This problem is about calculating the average waiting time for customers at a restaurant. Here are the key points:

1. There's a restaurant with a single chef.
2. Customers arrive at different times with food orders that take different amounts of time to prepare.
3. The chef can only prepare one order at a time.
4. If the chef is free when a customer arrives, they start preparing the order immediately.
5. If the chef is busy, the customer must wait until the chef finishes the current order.

The goal is to calculate the average waiting time for all customers.

Input:

• An array of customer orders, where each order is represented as [arrival_time, preparation_time].

Output:

• The average waiting time as a floating-point number.

Algorithm:

1. Initialize variables for the chef's available time and total waiting time.
2. Iterate through each customer order: a. Calculate the start time for the order (max of chef's available time and customer's arrival time). b. Calculate the waiting time for this customer (start time - arrival time + preparation time). c. Update the chef's available time (start time + preparation time). d. Add the waiting time to the total waiting time.
3. Calculate and return the average waiting time (total waiting time / number of customers).

#define ll long long

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers)
    {
        int n = customers.size();
        int endTime = 0;
        ll waitTime = 0;
        for (int i = 0; i < n; ++i)
        {
            endTime = max(customers[i][0], endTime) + customers[i][1];
            waitTime += endTime - customers[i][0];
        }
        return (double)waitTime / n;
    }
};

• T: $O(n)$
• S: $O(1)$