### Abinash's blog

By Abinash, 7 years ago,

Problem looks greedy to me !! But I can't find any way to solve it .

Most confusing line is "waiting time of a person who waits longest is minimized?"

Here waiting time means previous waiting time+new queue waiting time and waits longest consider by waiting time ?

"calculate the minimum waiting time for a person who waits the longest."

Here waiting time previous waiting time+new queue waiting time or new queue waiting time only ?

If anyone confused with my question , then please explain details forgot all the above. Anyone explain how to solution ?

• -3

 » 7 years ago, # | ← Rev. 5 →   0 This problem can easily solve by using priority_queue . Idea is simple i will always to try give opportunity those who are already waiting a lot . for that you can sort descending opder of already waited time . then push in priority_queue for next possible free time . Say Waited[] -> descending order sorted array of already waited people Que[] -> ascending order sorted array serving time in queue , M is the limit int idx = 0 ; priority_queue < int > pq ; // give us the sequence which will come next int Ans = -1 ; // check datatype for i = 1 -> M { pq.push(0); // intially all queue are ready } for i = 1 -> N { int extra = -pq.front(); int cur = waited[i] + extra ; if( Ans < cur ) Ans = cur ; int need = extra + Que[idx++] ; // next service time if(idx == M ) idx -= M ; pq.push(-need) ; } print -> Ans Main idea is something like that , you should get it now.
•  » » 7 years ago, # ^ |   0 Can u explain a case ? Suppose Waited[] -> 3 3 2 1 Que[] -> 2 3
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 sure , main idea is we will give service first to whom , who have already waited maximum time . for that first waited 3 min and that person will serve in que -1 ( which finish time is 2 min ) , he waited for only 3 min . right now my answer is 3 . then come second waited person who already waited 3 min and he will serve in que — 2 ( which finish time is 3 min ) and he also wait for 3 min ( no update in ans ) . then come person who waited for 2 min but right now no que is available so he have to wait , first que will finish its 1st task ( servicing 1st person ) in 2min , so 3rd person have to wait for ( 2 ( his previous waiting time ) + wait to go to que — 1 ) == ( 2 + 2 ) = 4 , which is higher then currently store ans 3 so ans will be updated . then come person 4 who is already waited 1 min , he have to wait another 3 min to receive his service from que 2 and his waiting time is ( 1 + 3 ) = 4 . no update . Final Ans is 4 .
•  » » » » 7 years ago, # ^ |   0 Thanks vai for you, reply !
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 I get AC ! Here is My Code !But I can't understand how ur code will work !shakil_AUST