This algorithm begins at Islamabad, and repeatedly tries to drive as far as possible without running out of gas.
current_distance = 0
current_stop = 0
stops = []
while current != lahore:
next_stop = 0
while distance(next_stop) - current_distance <= m:
next_stop = next_stop + 1
next_stop = next_stop - 1
current_stop = next_stop
current_distance = distance(current_stop)
add next_stop to stops
return stops
This is an optimal solution. To see this, we note that any sequence of stops that took less stops then the greedy algorithm would have to 'pass' the greedy algorithm at some point along the route.
Using induction, we can see that if the greedy algorithm is the farthest it can be after the first stop, and after the nth stop it is the farthest it could be given stop n - 1, then the greedy algorithm must be the farthest it can be for all stops along the route.
Although this algorithm has complexity O(n) and returns an optimal solution computationally, the route it returns may not be a very 'even' or 'smooth' route. In order to produce routes for actual use by people, more routes that space their stops more evenly would want to be considered.