Consider a long river, along which n houses are located. You can think of this river as an x-axis; the houses locations are given by their coordinates on this axis in a sorted order.

Your company wants to place cell phone base stations along the river, so that every house is within 8 kilometers of one of the base stations. Give an O(n)-time algorithm that minimizes the number of base stations used.

As well as giving the algorithm and showing that it runs in O(n) time, you must prove that it yields an optimal solution.