A group of n people are lying on the beach. The beach is represented by the real

Question

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 xi 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 N, and the i-th person is covered by that umbrella if xi I. Design a greedy algorithm for covering all people with the minimum number of umbrellas. The input consists of the integers x1, . . . , xn, and L. The output of your algorithm should be the positions of umbrellas. For example, if the input is x1 = 1, x2 = 3, x3 = 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]. The running time of your algorithm should be polynomial in n.

Explanation / Answer

Solution=======================

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.