最少基站覆盖：贪心算法解决边远山区移动电话服务问题

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

主要设计思想

使用贪心算法。从左到右扫描每个房子，对于每个未覆盖的房子i，选择右侧第一个未覆盖的房子j，使得j与i之间的距离不超过8千米，并在j处安装基站，将i~j之间的所有房子覆盖。重复此过程直到所有房子都被覆盖。

伪代码描述

将所有房子按照距离A的距离从小到大排序。
初始化：设置第一个基站在A点，将A~第一个房子之间的所有房子覆盖。
从左到右扫描每个房子i： a. 若i已被覆盖，则不做处理。 b. 若i未被覆盖，则选择右侧第一个未覆盖的房子j，使得j与i之间的距离不超过8千米，并在j处安装基站，将i~j之间的所有房子覆盖。
返回基站的总数和每个基站的位置。

正确性证明

该算法的贪心策略是每次选择右侧第一个未覆盖的房子，使得j与i之间的距离不超过8千米，并在j处安装基站。这样选择可以保证覆盖范围最小，即所需基站数量最少。因为如果选择右侧第二个未覆盖的房子k，则需要在i~k之间安装基站，此时覆盖范围会更大，所需基站数量会更多。所以该算法是正确的。

最坏情况下的时间复杂度函数

排序操作的时间复杂度为O(nlogn)，扫描每个房子并安装基站的时间复杂度为O(n)，所以算法的最坏情况下的时间复杂度为O(nlogn)。