We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Heap
  4. Minimum Average Waiting Time
  5. Discussions

Minimum Average Waiting Time

Sort by

recency

|

180 Discussions

|

  • macohip968
     + 0 comments

    Great problem! Reminds me of how Jun blades — razor-sharp and precise — can make all the difference in a kitchen. Just like Tieu optimizing wait times, the right tool (or algorithm!) cuts through inefficiency. Here, a min-heap for shortest cook time works like a Jun blade — sleek and effective.

  • manceraaxel
     + 0 comments
    import heapq

def minimumAverage(customers):
    customers.sort()
    n = len(customers)
    i = 0
    current_time = 0
    waiting_time = 0
    h = []

    while i < n or h:
        # Add all custoemrs with arrival time less or equal to current time so that no customer that arrives later is processed, as that is not valid.
        while i < n and customers[i][0] <= current_time:
            heapq.heappush(h, (customers[i][1], customers[i][0]))
            i += 1

        # From the clients whose arrival time is less than the current time, extract the one whose pizza has the least preparation time.
        if h:
            prep_time, arrival_time = heapq.heappop(h)
            current_time += prep_time
            waiting_time += current_time - arrival_time

        # In case there are no customers to process, move to next customer. :)
        else:
            current_time = customers[i][0]

    return waiting_time // n

  • phongthuypts
     + 0 comments

    This code passes all test cases

    public static long minimumAverage(List> customers) { // Write your code here // Assumption from the problem statement: // 1. The first order is always cooked first.

        customers.sort(new Comparator<List<Integer>>() {
        public int compare(List<Integer> o1, List<Integer> o2)
        {
            return o1.get(0) - o2.get(0);
        }
    });
    PriorityQueue<List<Integer>> cookQueue = new PriorityQueue<>();
    PriorityQueue<List<Integer>> orderQueue = new PriorityQueue<>(new Comparator<List<Integer>>()
    {
        public int compare(List<Integer> o1, List<Integer> o2)
        {
            return o1.get(1) - o2.get(1); // Sort based on cook time.
        }
    }); 
    long totalCookTime = 0;
    long totalWaitTime = 0;

    if(customers.isEmpty())
        return 0;
    // The first order is always cooked first
    cookQueue.add(customers.get(0));
    for(int i = 1; i < customers.size(); i++)
        orderQueue.add(customers.get(i));
    long firstOrderTime = cookQueue.peek().get(0);
    while(!cookQueue.isEmpty())
    {
        List<Integer> order = cookQueue.remove();
        int orderTime = order.get(0);
        int cookTime = order.get(1);
        totalCookTime += cookTime;
        totalWaitTime += (totalCookTime + firstOrderTime - orderTime);

        List<List<Integer>> holding = new ArrayList<>();
        while(!orderQueue.isEmpty() && orderQueue.peek().get(0) > (totalCookTime + firstOrderTime))
            holding.add(orderQueue.remove());
        if(!orderQueue.isEmpty())
            cookQueue.add(orderQueue.remove()); 
        if(!holding.isEmpty())
            orderQueue.addAll(holding); 

        // If there is a gap between order time and cook time (pizza oven idles)
        if(cookQueue.isEmpty() && !orderQueue.isEmpty())
        {
            cookQueue.add(orderQueue.remove());
            firstOrderTime = cookQueue.peek().get(0); //Reset the anchor point. 
            totalWaitTime = 0;
        }
    } 
    return totalWaitTime / customers.size();
}

  • dehaka
     + 1 comment

    lol the answer is long long but the question use int, if you're getting errors change int to long long in return type and in the main function

    O(nlog n)

    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();
}

  • dangquoctienvktl
     + 0 comments

    My C++ solution, it's not the best algorithm for this problem but it fits the way to think

    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();
}