struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        if (a.second == b.second) {
            return a.first > b.first;
        }
        return a.second > b.second;
    }
};

long long minimumAverage(vector<vector<int>> customers) {
    sort(customers.begin(), customers.end());
    long long totalTime = 0;
    long long currentTime = 0;
    int pizzaCooked = 0;
    int i = 0;
    vector<pair<int, int>> pendingOrders;
    while (pizzaCooked != customers.size()) {
        while (i < customers.size() and customers[i][0] <= currentTime) {
            pendingOrders.push_back({customers[i][0], customers[i][1]});
            push_heap(pendingOrders.begin(), pendingOrders.end(), Compare());
            i++;
        }
        if (pendingOrders.empty()) currentTime = customers[i][0];
        else {
            currentTime = currentTime + pendingOrders[0].second;
            pizzaCooked++;
            totalTime = totalTime + currentTime - pendingOrders[0].first;
            pop_heap(pendingOrders.begin(), pendingOrders.end(), Compare());
            pendingOrders.pop_back();
        }
    }
    return totalTime/customers.size();
}

long comp(vector<long> &a, vector<long> &b)
{
    return a[0] < b[0];
}
long minimumAverage(vector<vector<long>> customers)
{
    sort(customers.begin(), customers.end(), comp);
    multiset<long> waits;
    long visited = 0;
    auto leftIte = customers.begin();
    long res = 0;
    long timeline = customers[0][0];
    auto rightIte = customers.begin();
    while (visited < customers.size())
    {
        rightIte = upper_bound(leftIte, customers.end(),
                               timeline, [](long val, vector<long> &a)
                               { return a[0] > val; });
        auto it = leftIte;
        while (it != rightIte) {
            waits.insert((*it)[1]);
            it += 1;
        }

        if (waits.size() == 0)
        {
            timeline += (*leftIte)[0];
            continue;
        }
        long minVal = *waits.begin();
        res += waits.size() * minVal;
        waits.erase(waits.begin(), next(waits.begin()));
        it = leftIte;
        while (it < customers.end())
        {
            if (timeline >= (*it)[0])
            {
                it += 1;
            }
            else if ((*it)[0] <= timeline + minVal)
            {
                res += timeline + minVal - (*it)[0];
                waits.insert((*it)[1]);
                it += 1;
            }
            else
            {
                break;
            }
        }
        timeline += minVal;
        visited += 1;
        leftIte = it;
    }

    return res / customers.size();
}

2
0 26
5 13

def minimumAverage(customers):
    # Customers is a list of tuples. I assume it's already
    # sorted by i[0], the arrival time, but let's make sure.
    # We'll also need to know the total customer number in
    # order to calculate the average wait later on.
    
    customers.sort()
    cust_count = len(customers)
    
    # Since the minimum average wait will always be reached
    # by preparing the quickest pizza first, we want to store
    # the pizzas in a min heap sorted by required cook time.
    
    # As we start cooking, we'll pull customers off the list
    # and put them into a heap of waiting customers. We'll
    # also need to track time throughout the process to know
    # when to add to the heap or remove from it. And since
    # we're calculating average using the total number of
    # customers, we need a variable for total wait time to
    # divide by it.
    
    waiting = []
    time = 0
    wait_time = 0
    
    # This whole process will run until there are no more
    # customers in either list.
    
    while customers or waiting:
        
        # Move customers to waiting once they've ordered.
        # Flip tuple values for correct priority sort.
        while customers and time >= customers[0][0]:
            t_order, t_cook = customers.pop(0)
            heapq.heappush(waiting, (t_cook, t_order))
        
        # If we're waiting for orders, jump to the next.
        if len(waiting) == 0:
            time = customers[0][0]
            continue
        
        # We don't want to move one second at a time as
        # that would confuse priority. We want to think
        # of time in the form of pizzas cooked. So,
        # instead of incrementing time, we'll add the
        # cook time of the highest priority pizza, one at
        # a time. That will give the time the customer is
        # served, from which we subtract their order time
        # to know their wait and add it to the total wait.
        
        cook, order = heapq.heappop(waiting)
        time += cook
        wait_time += (time - order)
        
    # Use // to return only the integer part of avg time.
    return wait_time // cust_count

import heapq

def minimumAverage(customers):
    # customers = [(order_time, cooking_time)]
    customers.sort()  # Sort by order time, then cooking time
    number_of_customers = len(customers)
    current_time = total_wait = 0
    currently_waiting = []
    while customers or currently_waiting:
        # Move to a heap of currently-waiting customers (as of `current_time`)
        while customers and customers[0][0] <= current_time:
            order_time, cooking_time = customers.pop(0)
            heapq.heappush(currently_waiting, (cooking_time, order_time))
        if not currently_waiting:
            # no orders yet, so fast forward to next customer
            current_time = customers[0][0]
            continue
        # Cook the order that will finish the sooner (first item on the heap)
        cooking_time, order_time = heapq.heappop(currently_waiting)
        total_wait += current_time + cooking_time - order_time
        current_time += cooking_time
    return total_wait // number_of_customers