Problem of The Day: Average Waiting Time

Problem Statement

Intuition

My first thought on solving this problem is to simulate the process of serving each customer in the given order. Each customer has a specified arrival time and the time it takes to serve them. I need to keep track of the current time as each customer is served, ensuring that the next customer is only served after the current one is completed. By accumulating the total waiting time for all customers and dividing by the number of customers, I can compute the average waiting time.

Approach

To implement this approach, I will:

1. Initialize a variable to store the total waiting time (res).
2. Use a variable (next_start) to keep track of the time when the next customer can be served.
3. Iterate through the list of customers, processing each customer’s arrival time and service time.
4. For each customer:
   • If the current time (next_start) is greater than the customer’s arrival time, compute the delay and adjust the start time and service time accordingly.
   • Update the total waiting time.
   • Update next_start to the time when the current customer’s service is completed.
5. Finally, compute the average waiting time by dividing the total waiting time by the number of customers.

Complexity

• Time complexity: The time complexity of this approach is \(O(n)\), where (n) is the number of customers. This is because we iterate through the list of customers once.
• Space complexity: The space complexity is \(O(1)\) as we are using a constant amount of extra space regardless of the input size.

Code

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        res = 0
        next_start = 0
        for start, time in customers:
            if next_start > start:
                delta = next_start - start
                start += delta
                time += delta
            res += time
            next_start = start + time - delta
        return res / len(customers)

Editorial

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        next_idle_time = 0
        net_wait_time = 0

        for customer in customers:
            # The next idle time for the chef is given by the time of delivery
            # of current customer's order.
            next_idle_time = max(customer[0], next_idle_time) + customer[1]

            # The wait time for the current customer is the difference between
            # his delivery time and arrival time.
            net_wait_time += next_idle_time - customer[0]

        # Divide by total customers to get average.
        average_wait_time = net_wait_time / len(customers)
        return average_wait_time