Consider the following problem that requires a greedy algorithm solution. Suppose there is a long straight road in a rural community, with n houses spread far apart along the road. Positions along the road are specified by distance in kilometers from one end to the other, where distance d > 0. The position of the k^th house along the road is given by d = h_k.

Problem. Given the house locations, h_k where k= 1..n and the range R > 0, the problem is to determine how to place the minimum number of cell phone towers along the road, a distances of t_j where j=1..J, so that each of the houses can get service from at least one of the towers. We wish to minimize J.

Assume the following:

a cell tower has a range of R kilometers where R > 0

If the j^th tower is placed at kilometer t_j along the road, then any house k with |h_k ? t_j | ? R would have service from that tower.

Assume the indices k are provided in the order the houses first requested service from the cell phone company.

[5 points] Describe a reasonably efficient greedy algorithm that generates an optimal solution for the general problem stated above. The algorithm must find the locations of and the minimum numbers of the cell phone towers along the road. Justify your answer. Note the towers can be built at any distance d along the road, and not just beside houses. Provide a description and the pseudocode for the algorithm.

[5 points] Illustrate how your algorithm works on a simple example such as requiring three cell phone towers in a scenario.

[5 points] Runtime order. Give a big-O estimate of the runtime of your algorithm. Briefly explain how you arrived at this estimate.