假设您必须从伊斯兰堡开车到拉合尔。开始时，您的油箱已满。当你的油箱装满时，它可以容纳足够的汽油行驶m数英里，并且你有一张地图，显示了沿途加油站之间的距离。设d1 < d2 < … < dn为沿途所有加油站的位置，即di伊斯兰堡到加油站的距离。相邻加油站之间的距离最多为m几英里。此外，最后一个加油站和拉合尔之间的距离最多只有m几英里。
您的目标是沿途尽可能少地加油站。给出一个贪心算法（以伪代码形式）来确定您应该在哪些加油站停车。
你的解决方案是最优的吗？您的解决方案的时间复杂度是多少？
该算法从伊斯兰堡开始，并反复尝试在不耗尽汽油的情况下尽可能地行驶。
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
这是一个最佳解决方案。为了看到这一点，我们注意到任何停靠点少于贪婪算法的停靠点序列都必须在沿路线的某个点“通过”贪婪算法。
使用归纳法，我们可以看到，如果贪心算法在第一个停靠点之后最远，并且在第 n 个停靠点之后，它是最远的，它可以被给予第 n - 1 个停靠点，那么贪心算法必须是它可以最远的地方沿途所有站点。
尽管该算法的复杂度为 O(n) 并通过计算返回最优解，但它返回的路线可能不是非常“均匀”或“平滑”的路线。为了生成供人们实际使用的路线，需要考虑更多将停靠点间隔更均匀的路线。