Algorithms question, thanks! A group of n people are lying on the beach. The bea

Question

Algorithms question, thanks!

A group of n people are lying on the beach. The beach is represented by the real line R and the location of the i-th person is some integer x, e Z. Your task is to prevent people from getting sunburned by covering them with umbrellas. Each umbrella corresponds to a closed interval I - [a, a +L] of length L E N, and the i-th person is covered by that umbrella if x, e I. Design a greedy algorithm for covering all people with the minimum number of umbrellas. The input consists of the integers x1,... ,^n, and L. The output of your algorithm should be the positions of umbrellas. For example, if the input is x1 = 1, x2-3, x,-5, and L-2, then an optimum solution is the set of two umbrellas placed at positions 2 and 5, covering intervals [1,3] and [4, 6] 1 2 3 4 5 6 The running time of your algorithm should be polynomial inn

Explanation / Answer

i=0

j=0

while(i<n)

{

if(a[i]==1)

{

umb[j] = i;

j++;

i+=3;

}

else

{

i++;

}

}

The time taken by this algorithm is O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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