Notation. For a graph G we denote by V(G) its set of vertices, and by E(G) its s

Question

Notation. For a graph G we denote by V(G) its set of vertices, and by E(G) its set of edges. Problem 1: A day at the beach. 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 xIE Z. Your task is to prevent people from getting sunburned by covering them with umbrellas. Each umbrella corresponds to a closed interval 1 = [a, a + L] of length L E N, and the i-th person is covered ign a greedy algorithm for number of umbrellas. The input consists of the integers xi,...,^n, 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

#include #include #include int solve(std::vector& people, int umbrellaCoverage) { std::sort(people.begin(), people.end() ); int answer = 0; double umbrellaReach; for(const auto& p : people) { if(answer == 0) { answer += 1; umbrellaReach = p + umbrellaCoverage; } else { if(p

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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