here is the code:
public int findStartPumpIndex(int[][] pumpDistance){
int leftGas = 0;
int start = 0;
//Find the potential start
for(int i=0; i<pumpDistance.length; i++){
int addGas = pumpDistance[i][0];
int consumeGas = pumpDistance[i][1];
int left = leftGas + addGas - consumeGas;
if(left >= 0){
leftGas = left;
}else {
leftGas = 0;
start = i+1;
}
}
//if we failed find a start at last, not solution
if(start >= pumpDistance.length)
return -1;
//otherwise continue to go, until back to start
for(int i=0; i<start; i++){
int addGas = pumpDistance[i][0];
int consumeGas = pumpDistance[i][1];
int left = leftGas + addGas - consumeGas;
if(left > 0){
leftGas = left;
}else {
return -1;
}
}
return start;
}
On Sun, Jan 30, 2011 at 9:55 AM, Wei.QI <qiw...@gmail.com> wrote:
> For any gas pump, when your car arrives, it contains 0 or more gas.
> So, for each gas pump, the worst case is starting from that pump.
>
> Then, if we starting from pump A1, passed A2 - Ak and failed at Ak+1. for
> A1 to Ak, we can not pass Ak+1 starting from any of them. So we try start
> from Ak+1.
>
> This could be solved in liner time. finding a possible start pump use O(n)
> and prove it use another O(n).
>
> -weiq
>
>
> On Sat, Jan 29, 2011 at 9:47 PM, nishaanth <nishaant...@gmail.com> wrote:
>
>> @Wei.Qi.... Can you clarify when your algorithm terminates and also what
>> is the running time of the algorithm ?
>>
>>
>> On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang <zhangyunq...@gmail.com> wrote:
>>
>>> can you prove it?
>>>
>>> On Jan 29, 2011 6:38 PM, "Wei.QI" <qiw...@gmail.com> wrote:
>>> >
>>> > Starting with any pump A, try to finish the circle, if at pump B that
>>> can not reach pump B+1, it means all pumps from A to B can not finish the
>>> circle (it will go broke at pump B), then just start with B+1. After go
>>> through all the pumps start from some pump, we got an answer. if we go back
>>> to pump A and later, still can not find an answer, there is no answer.
>>> >
>>> > On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava <
>>> richi.sankalp1...@gmail.com> wrote:
>>> >>
>>> >> I'm sure you have misstated the problem statement
>>> >>
>>> >> just find out the total path length and return the first petrol pump
>>> >> which gives you the required milage
>>> >> go greedy
>>> >>
>>> >> On Jan 28, 5:09 pm, bittu <shashank7andr...@gmail.com> wrote:
>>> >> > There are N petrol pumps along a circular path. Every petrol pump
>>> >> > gives some amount of fixed petrol. Need not to be unique and in no
>>> >> > particular order means it is random. We have a car and we need to
>>> find
>>> >> > a petrol pump which can provide so much of petrol that we can take a
>>> >> > full of the circle. Mileage of car is fixed.
>>> >> > Distance between adjacent petrol pumps are given.
>>> >> >
>>> >> > Thanks & Regards
>>> >> > Shashank
>>> >>
>>> >> --
>>> >> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> >> To post to this group, send email to algogeeks@googlegroups.com.
>>> >> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> >> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>> >>
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> > To post to this group, send email to algogeeks@googlegroups.com.
>>> > To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> > For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> S.Nishaanth,
>> Computer Science and engineering,
>> IIT Madras.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
