Abinash's blog

Greedy Problem Help Needed !
By Abinash, 9 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

»
9 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.

→ Reply
  • »
    »
    9 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

    → Reply
    • »
      »
      »
      9 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 .

      → Reply