Discussion on Minimum Average Waiting Time Challenge

Sort by

recency

|

179 Discussions

|

3 weeks ago+ 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

3 months ago+ 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();
}

2 years ago+ 0 comments

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

2 years ago+ 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();
}

2 years ago+ 0 comments

I get that you cannot see future orders as in the solution must be online, but what's stopping me from delaying an order and not cook any pizzas at the moment to bet on the possibility that it could get me a lower average waiting time?

Example:

2
0 26
5 13

Expected answer is 60/2=30, but if you delay the first customer's order and cook the second customer's pizza first you can get 57/2=28.5.

The expected solution assumes that you should always cook pizzas as long as you have an order, however I do not see this in the problem statement. Am I making any sense?

(Unrelated but what's up with the spam checker?)

EDIT: Found this comment https://www.hackerrank.com/challenges/minimum-average-waiting-time/forum/comments/124605, looks like I'm not alone :)

Sort by

|

179 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge