Consider a long straight road with n buildings scattered sparsely along its leng

Question

Consider a long straight road with n buildings scattered sparsely along its length. Let x1 < x2 < . . . < xn denote the locations of these buildings, measured in meters from the left endpoint of the road. Design a greedy algorithm that will place the minimum number of cell towers along this road so that every building is within four miles of one of the towers. Explain your algorithm on a figure, provide pseudocode and state its asymptotic running time. Prove that your greedy algorithm is correct.

Explanation / Answer

Assmption: x1 to xn is in sorted order

and x1 to xn is the distance between buildings in miles

Algorithm:

1. Get value of k such that xk <= 4 (Filtering out all those building for which distance is more than 4)

2. Start placing buildings in reverse order from xk to x1

3. By greedy approach we just want to place minimum building so, place buildings on the road from max possible to 1, hence reducing number of building which can be places

Asymptotic running time = O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.