Average Waiting Time - Leetcode Solution

Problem Statement:

Given an array of n integers representing the arrival times of the customers in a queue and an array of n integers representing the time required to serve each customer, calculate the average waiting time of all the customers.

Solution:

One way to solve this problem is to simulate the customer queue and track each customer's wait time. We can maintain a variable called current_time that represents the current time in the simulation. We can also maintain a variable called next_available_time that represents the time when the server will be available to serve the next customer. At the beginning, we set the current_time to the arrival time of the first customer and the next_available_time to the sum of the current_time and the service time of the first customer. Then, for each subsequent customer, we compare their arrival time with the next_available_time. If the arrival time is greater than or equal to the next_available_time, the customer can be served immediately and we update the next_available_time to the sum of the current_time and the service time of the customer. Otherwise, the customer has to wait in the queue and we update their wait time by subtracting their arrival time from the current_time and add it to a variable called total_wait_time. Finally, we return the average wait time by dividing the total_wait_time by the number of customers.

Here's the Python code for this solution:

def average_waiting_time(arrival: list[int], service: list[int]) -> float: n = len(arrival) current_time, next_available_time, total_wait_time = 0, 0, 0 for i in range(n): if arrival[i] >= next_available_time: next_available_time = arrival[i] + service[i] else: total_wait_time += next_available_time - arrival[i] next_available_time += service[i] current_time = arrival[i] return total_wait_time / n

This code has a time complexity of O(n), where n is the number of customers.

1