Problem : Link
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 ?
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 .
Main idea is something like that , you should get it now.
Can u explain a case ? Suppose Waited[] -> 3 3 2 1 Que[] -> 2 3
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 .
Thanks vai for you, reply !
I get AC ! Here is My Code !
But I can't understand how ur code will work !
shakil_AUST