greedy algorithm pseudo code [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

Suppose you have to drive from Islamabad to Lahore. At the start, your gas tank is full. Your gas tank, when full, holds enough gas to travel m miles, and you have a map that gives distances between gas stations along the route. Let d1 < d2 < … < dn be the locations of all the gas stations along the route, where di is the distance from Islamabad to the gas station. The distance between neighboring gas stations is at most m miles. Also, the distance between the last gas station and Lahore is at most m miles.

Your goal is to make as few gas stops as possible along the way. Give a greedy algorithm (in pseudo-code form) to determine at which gas stations you should stop.

Is your solution optimal? What is the time complexity of your solution?

Answer 1

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.