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 <sweetdivya....@gmail.com> 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 <technic....@gmail.com> 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 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.