Following approach works by calculating the least amount of fuel at
station i
min_fuel[n] = 0 //indicates least amount of fuel that should be in
car when it is at station i
d[i] = distance b/w station i+1 and i
l[i] = liters available at station i
for (i=n-1 to 1)
{
if (l[i] < (d[i] + min_fuel[i+1])) //assuming l ltrs can cover l
units of distance
min_fuel[i] = (d[i] + min_fuel[i+1]) - l[i]
else
fuel[i] = 0
}
current_fuel = m
for (i=1 to n)
{
if (current_fuel < min_fuel[i])
{
current_fuel += l[i]
if (current_fuel > m)
current_fuel = m
}
current_fuel = current_fuel - d[i]
}
On Jan 22, 9:40 pm, Divya Jain <[email protected]> wrote:
> if u can take only a certain amount of fuel from a particaular station ie
> station xi can provide li amoutn of fuel.. then wat?
>
> On 22 January 2011 13:46, Terence <[email protected]> wrote:
>
> > Greedy-Approach.
> > Refueling only when you have to.
>
> > On 2011-1-22 15:59, snehal jain wrote:
>
> >> Suppose you want to travel from city A to city B by car, following a
> >> fixed route. Your car can travel m miles on a full tank of gas, and
> >> you have a map of the n gas stations on the route between A and B that
> >> gives the number of miles between each station.
> >> Design an algorithm to find a way to get from A to B without running
> >> out of gas that minimizes the total number of refueling stops, in O(n)
> >> time.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%[email protected]>
> > .
> > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
