Consider a straight road with houses scattered very sparsely along it. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations. Give a greedy algorithm that achieves this goal, using as few base stations as possible. Compute the worst-case run-time complexity of your algorithm and prove the optimality of the solution it gives.
Assume that the road is a straight line with a western end and an eastern end. The input would be the distance of each house from the western end. A sample input would be:
House number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Distance 10 36 21 30 47 44 16 31 25 54 13 39 6 19 53
The output should be the locations of the base stations. For this example, you'll need 5 base stations.