设有一条边远山区的道路AB，沿着道路AB分布着n所房子.这些房子到A的距离分别是d1,d2,……… ,dn，其中d1<d2<...<dn. 为了给所有房子的用户提供移动电话服务，需要在这条道路上设置一些基站.为了保证通信质量，每所房子应该位于距离某个基站的4千米范围之内.设计一个算法找到基站的位置，并且使得基站总数达到最少

这个问题可以通过贪心算法来解决。

首先，在A点放置一个基站。然后，从A开始，找到第一个距离A的距离大于4千米的房子，将基站放置在这个房子的左侧4千米范围内。接下来，在第一个基站右侧4千米范围之外找到第一个距离上一个基站的距离大于4千米的房子，将基站放置在这个房子的左侧4千米范围内。重复这个过程，直到所有的房子都在某个基站的4千米范围之内。

算法的正确性可以通过反证法证明。假设存在一种更优的放置基站的方案，需要比当前方案使用更少的基站。考虑对于这个方案中距离最远的两个基站A和B，它们之间存在一个距离大于8千米的房子C。由于距离A的距离小于4千米，距离B的距离小于4千米，所以C的距离必然大于4千米。根据我们的算法，在A和B之间应该放置一个基站，以覆盖C。因此，这个更优的方案与我们的方案矛盾，因此我们的算法是正确的。

时间复杂度为O(n)，因为算法只需要遍历一次所有的房子。