Bank Average Waiting Time

In a bank, customers queue up to deposit or withdraw money. Typically, they are served on a First Come First Served (FCFS) basis. However, the bank manager, aiming to reduce the average waiting time for customers, has devised a new technique where customers can be served in any order.

Each customer requires varying amounts of time to complete their transaction. A program should accept N pairs of integers as input. Each pair will consist of an arrival time followed by the time taken to either deposit or withdraw money. The program should output the minimum average waiting time T for all the N customers, based on the new service method the bank manager has introduced.

Boundary Conditions:
1 <= N <= 10^4
0 <= Arrival time of each customer <= 10^9
1 <= Waiting time of each customer <= 10^9

Input Format:
The first line contains N.
The subsequent N lines each contain two integers separated by a space.

Output Format:
The first line contains T.

Example:
Input:
3
0 4
1 7
2 5

Output:
8

Explanation:
In the First Come First Served technique,
The waiting time of the first customer who arrives at 0th second is 4 seconds (0th sec to 4th sec). The waiting time of the second customer who arrives at 1st second is 10 seconds (1st sec to 11th sec).
The waiting time of the third customer who arrives at 2nd second is 14 seconds (2nd sec to 16th sec).
Here the total waiting time is 28 seconds (4 + 10 + 14).
The average waiting time is 9 seconds (28/3).

In the new serving technique introduced by the bank manager,
The waiting time of the customer who arrives at 0th second is 4 seconds (0th sec to 4th sec).
The waiting time of the customer who arrives at 2nd second is 7 seconds (2nd sec to 9th sec). The waiting time of the customer who arrives at 1st second is 15 seconds (1st sec to 16th sec). Here the total waiting time is 26 seconds (4 + 7 + 15).
The average waiting time is 8 seconds (26/3).
So 8 is printed as the output.

Another Example:
Input:
4
0 5
4 8
3 3
1 6

Output:
10

import heapq

def minimum_average_waiting_time(customers):
    customers.sort(key=lambda x: x[0])

    curr_time = 0
    total_wait_time = 0
    wait_queue = []
    i = 0
    n = len(customers)

    while i < n or wait_queue:
        while i < n and customers[i][0] <= curr_time:
            heapq.heappush(wait_queue, customers[i][1])
            i += 1

        if wait_queue:
            processing_time = heapq.heappop(wait_queue)
            total_wait_time += curr_time + processing_time - customers[i-len(wait_queue)-1][0]
            curr_time += processing_time
        else:
            curr_time = customers[i][0]

    return total_wait_time // n

N = int(input())
customers = [tuple(map(int, input().split())) for _ in range(N)]
print(minimum_average_waiting_time(customers))

Question asked by: Crazy Coder