Abinash's blog

By Abinash, 10 years ago, In English

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 ?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
10 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u explain a case ? Suppose Waited[] -> 3 3 2 1 Que[] -> 2 3

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 .