The greedy approach which is used here is explained below.

For finding the stops where the user should make a stop, first declare a dynamic vector to store all the stops.

Take a flag as a starting point and iterate over all the stops to find out if the user will be able to make it to the stop or not provided he is only able to make $d$ miles per day.

Subtracting the starting point's distance from the first gives us the overall distance between those two points and if it is less than $d$, the user is obviously willing to go a few miles further than that stop. So in the program subtracting the next stop's distance from the first, we can find out, if it is less than $d$ or not. If it is, then the program will proceed further to the next stop. If not, then that stop will be added to the answer vector because the user will not be able to go any further. Besides, that stop will be stored in the flag variable because that point is now has become the user's starting point.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.