- 0of 0 votes
I came across this in a contest and haven't been able to solve it yet.
You are located at point 0 having p units of petrol, and you need to reach a point N. car consumes one unit of petrol every unit of distance it travels. Find minimum number of stops you need to make to reach the end.
3 , 15
6 , 4
8 , 5
15 , 6
output is 1 is distace to travel is 20 and inital petrol is 17.
The town is situated at co-ordinate 0. All the other distances are given with respect to town's location.
I initally though about the greedy approach but that only working in case you have enough petrol in petrol station to reach the next station.