# Minimum Average Waiting Time

# Minimum Average Waiting Time

- B
BTANguyen + 5 comments This is misleading and the problem statements are unclear. Customer's arrival times are not in order. The scenerio shows real restaurant situation, but customer's arrival times are out of order. In real life, how could customer A arrives at time X; a moment later, customer B arrives at time X - 2?

mestoyaburriendoAsked to answer + 1 comment I mean, I know what you are saying but the problem is what it is :).

Having said that, just use a min-heap when parsing the results and you'll have them in order.

- VG
vidushig2 + 2 comments we need to use dp.

ccordero + 1 comment what is dp?

- TP
tapu_tapan99 + 1 comment Dynamic Programming

ccordero + 1 comment What's that?

- TP
tapu_tapan99 + 0 comments Google it. https://www.hackerrank.com/domains/algorithms/dynamic-programming See this Hackerrank problems on dp.

durumu + 1 comment Definitely not necessary to use dynamic programming. Can be solved in O(n log n) by creating and sorting a list of the (arrival, cook_time) pairs by arrival, then using a small min-heap, sorted by cook time, to keep track of the people who are currently in the pizza shop (i.e. whose arrival time < the total time elapsed) by using the list as a stack. This is O(n log n + n log p) time where p is the number of people in the shop at any given time, and since p <= n, the algorithm is O(n log n). Here is the code:

`from heapq import heappush, heappop tasks = [] N = int(input()) for _ in range(N): arrival, cook_time = map(int, input().split()) tasks.append((arrival, cook_time)) tasks.sort(reverse=True) pq = [] time_waiting = 0 current_time = 0 while tasks or pq: while tasks and tasks[-1][0] <= current_time: heappush(pq, tasks.pop()[::-1]) if pq: current_task = heappop(pq) current_time += current_task[0] time_waiting += current_time - current_task[1] else: heappush(pq, tasks.pop()[::-1]) current_time = pq[0][1] print(time_waiting // N)`

- VN
vlad_nalimov + 0 comments Nice, clean and easy-to-read code, thanks for sharing!

JimB6800 + 0 comments Agreed. Especially since the problem statement indicates that the cook will not know about future orders. Makes is pretty clear that the input should be time ordered.

danbuscaglia + 2 comments Keep in mind - you have to manage the heap not just in the typical order (pizza cooking time) but also ensure enough time has passed for the order to have taken place. You will have to implement some sort of way to manage the heap to pop the node that has the lowest cook time, but also is a valid order.

- AD
Anupam_De + 1 comment Can you please help me how to manage heap in such a way?

danbuscaglia + 0 comments something like this: def get_next_valid_order(t, q): restoreitems = [] pizza_cook_time, start_time = q.next() while start_time > t: restoreitems.append((pizza_cook_time, start_time)) pizza_cook_time, start_time = q.next() if restoreitems: for item in restoreitems: q.push(item[0], item[1]) return pizza_cook_time, start_time

- MV
desavera + 0 comments Folks, it must be a constant time access data structure. A heap will not pass the large data tests !

Tuxdude + 0 comments Agreed Completely. This is another one of those problem statements with ambiguity.

Also given that the 2 input test cases have the inputs time ordered you take it for granted assuming the problem mimics the real life behavior.

- DR
dlr2dlr2 + 0 comments Yes, beware that you need to sort the input in arrival time - I suppose that its not stated that they are not in such order, so it would be a bad assumption perhaps, but the examples show in order arrival data so it might be misleading

- VK
Virendra13 + 6 comments I think, testcases is not handling the following case:

here n=2 and T(1) > L(0),

2

0 9

10 4

its answer should be 6. But my program (passed all testcases)is giving 9 (wrong result).

- AA
temld4Asked to answer + 0 comments **Endorsed by Virendra13**Good one. In my program I took into account such cases, but it turned out this part of program did not work properly due to extra increment (thank u for debug material:) ). Despite this it had passed all test cases before i made corrections. It seems there's no testcase which covers that.

YogendraA_C_R + 2 comments how ans should be 6 ? i think ans should be zero.

- DR
dlr2dlr2 + 0 comments Maybe they updated it, but I completed all tests with the correct values. That is, do not assume that the schedule is packed, there can be gaps in using the oven :)

piyushmishra + 0 comments why 9?

- MV
desavera + 0 comments This is a very tricky test case and was incorporated to the tests list in deed !

- DP
dpruthi + 0 comments thanks for this input, helped me to get what was missing..

- T
tgor_ + 0 comments Testcases are garbage. I guess that author wanted to annoy users, because otherwise why didn't he mentioned that orders are not in order (that even sounds ridiculous!). Dear author: if you wanted such constraints then please mention this somewhere in the problem statement, otherwise this is just pain in the ass.

- M
mehtabhavesh9 + 5 comments This is quite a challenging problem with some tricky cases to deal with so some hints are in order. Before reading the hint on how to solve the problem, couple of points to note:

Pizza orders are not listed in the order of arrival. Your program should be able to deal with that.

Assume that if you have an order that has arrived but has a long completion time you should process that order. You don't have to wait for the next order that has much shorter completion time if it hasn't arrived yet. Consider this test case which is slight variation on the test case in the problem:

3 0 9 1 3 2 5

Here you should begin processing the first order right away. You will complete all orders with total wait time of 35 with an average wait time of 35/3 = 11. If you just don't process the first order and wait for the 2nd order then you can finish all orders with a total wait time of 28 with an average of 28/3 = 8. The correct answer is 11 and not 8 for this problem.

Now here's the HINT (Read only after you have struggled with the problem for more than an hour):

a. Maintain two queues. One for all the orders prioritized by arrival time. The second one for all orders prioritized by completion time with the shortest order at the head of the queue.

b. Read all the orders in sequence and fill the arrival time queue (first queue).

c. Have a loop that ticks time.

d. For every time tick in the loop see if there are any orders that have arrived by this time from the first queue. If there are then transfer them to the second queue (ordered by completion time) for processing (cooking).

e. Pick the top order from the second queue to process (cook the pizza). If you process the order then tick the time by the time it takes to cook that pizza. If you didn't have any order to process then tick the time by 1 unit. Keep track of total time to process the orders as you process them.

e. Repeat Steps b to e till all orders are processed.

f. Compute the average wait time and print it.

Hope this much explanation is ok to post on the forum. If this is too much let me know and I can condense it further. If there is an easier way to solve the problem then let me know that too.

harrynp21 + 0 comments Refer to a line in your post. "e. Repeat Steps b to e till all orders are processed."

If I understand your algorithm correctly, repetition should start from steps c, instead of b, to e. Correct me if I'm wrong.

- SL
slagree + 0 comments For part e, where you say "If you didn't have any order to process then tick the time by 1 unit", this is unneccesary. You can just look at the next order in your first queue and use its order time as the next time. If you jump to that time, you skip a bunch of unnecessary incrementing.

gulli1007 + 1 comment #include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; struct customer { long long arrTime; long long cookTime; long long index; }; bool compare( customer& a, customer& b) { return a.arrTime<b.arrTime; } struct Compare1 { bool operator()(customer a,customer b) { return a.cookTime>b.cookTime; } }; struct Compare2 { bool operator()(customer a,customer b) { return a.arrTime>b.arrTime; } }; int main() { vector<customer>c; vector<bool>done; long long n; cin>>n; for(long long i=0;i<n;i++) { customer cust; cin>>cust.arrTime; cin>>cust.cookTime; cust.index=i; c.push_back(cust); done.push_back(false); } priority_queue<customer,vector<customer>,Compare2>arrivalList; for(long long i=0;i<n;i++) arrivalList.push(c[i]); priority_queue<customer,vector<customer>,Compare1> waitList; vector<long long>tat(n); vector<long long>ct(n); //next step- priority queue work starts long long count=0; long long totalTime=0; while(count!=n) { while(!arrivalList.empty() && arrivalList.top().arrTime<=totalTime) { waitList.push(arrivalList.top()); arrivalList.pop(); } customer next; if(!waitList.empty()) { next=waitList.top(); //cout<<"Job "<<next.index<<endl; waitList.pop(); totalTime+=next.cookTime; ct[next.index]=totalTime; done[next.index]=true; count++; } else if(!arrivalList.empty()) { next=arrivalList.top(); //cout<<"Job "<<next.index<<endl; arrivalList.pop(); totalTime+=next.cookTime; ct[next.index]=totalTime; done[next.index]=true; count++; } } long long sum=0; for(long long i=0;i<n;i++) { tat[i]=ct[i]-c[i].arrTime; sum+=tat[i]; } cout<<sum/n; return 0; }

Hi. I also thought of and implemented something similar. it's passing sample test cases and cases 10,11 and 12. Rest of the cases are failing. could u pls help?

LukaszJ + 0 comments else if(!arrivalList.empty()) { next=arrivalList.top(); //cout<<"Job "<<next.index<<endl; arrivalList.pop(); totalTime+=next.cookTime; ct[next.index]=totalTime; done[next.index]=true; count++; }

That part is wrong when there is no customer at time 0 and we have to wait for first customer and when there is a gap between customers when there is no customer to serve.

maheshreddym + 0 comments yep perfect even i thought of same thng and coded with the samelogic but my logic isnt working

- AU
adi7tya + 0 comments is it necessary to start from first order if it starts from 2 order first then 3 order then at last the first order average is 9

johnjinkim1 + 0 comments Just wanted to expand on this a bit since it would help me clarify my own thoughts!

3 0 3 1 9 2 6

## Base Case:

- The first pizza will always be made and cooked first, finishing at time of 3
- At time of 3, Customer 1 and 2 have arrived.
- At this point, since 3 > 1 and 3 > 2, this is where the decision is made.
- We choose customer 2, since 6 < 9
Once customer 2 is finished, the current time is now 3+(3-2 + 6) -> 3+7 3 is curr time, and we subtract 2 from it since customer 2 arrived at 2, so rather than adding just 6 (the time to cook customer 2's pizza), we need to add 3-2 which is 1. If customer 2 arrived at time 3, then we could have just added 3+6.

Then add the last value since it is the last customer 3+7+(9+9-1)

Lets define Minimum Average Waiting Time as MAWT.

## Assumptions:

There are 2 time sources we need to keep track of, the incremental time representing arrivals (i.e. 0,1,2), and the current time done in strides (arrival time + time to cook)

- The incremental time representing arrivals should be used to check IF we can add a customer to the waiting queue (since we CANNOT consider a pizza IF the customer hasnt even arrived yet!!!)
- IF the waiting queue is NOT EMPTY, pop the top and add its value to the CURRENT TIME DONE IN STRIDES (MAWT = current time + time to cook - time arrived)
- The finish case is if the waiting list is empty AND the incremental time representing arrivals is equal to n(number of customers that come in)

## NOTE:

- Current time and MAWT are NOT the same thing.
- Current time is the time to cook times added together (3+6+9)
- MAWT is the current time WITH the waiting time added to it (3 + (6+3-2) + (9+9-1))

Hope this helps, and happy coding :3

rcashie + 0 comments Heads up...

Even though the problem states that the '

*Cook does not know about future orders*' the orders themselves are**not**sorted by time... :S.Also, the first pizza order does not always start at t = 0. That tripped me up big time.

- YG
nj1308 + 0 comments Try to avoid the rookie mistake. Use

*long*instead of*int*for time accumulators.Should have saved 20min for me, had I knew.

- KT
kittenintofu + 3 comments For those who are struggling with this problem: one of a possible approach is to solve it by 2 priorityQueue: all_customers, waiting_list. all_customers is sorted by arrival time, waiting_list is sorted by cooking time.

- First, add all the customers to all_customers.
Then start the while loop. If, waiting_list is empty(which will be true when (a): you first enter the loop, or (b): nobody comes when the last pizza was being cooked), pop a customer from all_customers as the next customer. Else, pop a customer from waiting_list as the next customer.

Then pop from all_customers to waiting_list until the peek of all_customers's arrival time is later than the current pizza is done cooking.

Hope it helps

- RM
rajeevd97 + 1 comment do we make a separate class for customers?

- KT
kittenintofu + 0 comments yes, at least that's how I implemented it

- JL
jeffffffffff + 0 comments [deleted] - MM
mmanimanasa + 0 comments we need specific pizza which take specific time for a specific customer.if we sort the cooking time.then there is no guarante that first customer is served with that least time pizza is his ordered pizza.i may be understandin your solution statement wrong.pls shed some light here!

- H
harshagr + 3 comments I am using C++ language. Some of the test cases have some very large numbers. To calculate average waiting time, either we can first calculate total time and then divide it by n or we can divide by n while adding any number to the total time. In the first approach, the total time becomes very large and goes out of range of even long and in second approach, there is some round-off error which gets added each time and final answer might be little smaller than the correct answer. I am stuck at this. Can anybody please help? Thanks in advance!

Zorik + 0 comments [deleted]- RK
rajeshkumarsr + 0 comments 'long' is working for me. I am initializing large datastructures dynamically.

Sid_S + 0 comments long long is guaranteed to be at least 64 bits, long is not.

- Z
zbart + 0 comments public class MinimumAverageWaitingTime { public static void main(String[] args) { Scanner in = new Scanner(System.in); int numOfCustomers = in.nextInt(); Customer[] customers = new Customer[numOfCustomers]; for (int i = 0; i < numOfCustomers; i++) { int orderTime = in.nextInt(); int cookTime = in.nextInt(); customers[i] = new Customer(orderTime, cookTime); } in.close(); Arrays.sort(customers, Comparator.comparingInt(o -> o.orderTime)); Queue<Customer> waitTime = new PriorityQueue<>(); long currentTime = 0L; long totalWaitTime = 0L; int index = 0; while (!waitTime.isEmpty() || index < customers.length) { while (index < customers.length && customers[index].orderTime <= currentTime) { waitTime.add(customers[index]); index++; } if (waitTime.isEmpty()) { currentTime = customers[index].orderTime; continue; } Customer served = waitTime.poll(); currentTime += served.cookTime; totalWaitTime += currentTime - served.orderTime; } System.out.println(totalWaitTime / customers.length); } static class Customer implements Comparable<Customer> { int orderTime; int cookTime; public Customer(int orderTime, int cookTime) { this.orderTime = orderTime; this.cookTime = cookTime; } @Override public int compareTo(Customer o) { if (this.cookTime > o.cookTime) { return this.orderTime; } else return -1; } } }

Sort 90 Discussions, By:

Please Login in order to post a comment