Let X be a finite set of real numbers. Consider the problem of finding the fewes

Question

Let X be a finite set of real numbers. Consider the problem of finding the fewest number of unit length intervals a_i lessthanorequalto x lessthanorequalto a_i + 1 such that every element of X is in some interval. (For example, if X = {0.3,0.7, 3.8, 4.5} an optimal solution could consist of two intervals: 0 lessthanorequalto x lessthanorequalto 1 and 3.5 lessthanorequalto x lessthanorequalto 4.5.) Explain why this problem has the greedy-choice property, and describe a greedy algorithm to solve it.

Explanation / Answer

First we sort the set of n points {x1, x2, ..., xn} to get the set Y = {y1, y2, ..., yn} such that y1 y2 ... yn. Next, we do a linear scan on {y1, y2, ..., yn} started from y1. Everytime while encountering yi , for some i {1, ..., n}, we put the closed interval [yi , yi + 1] in our optimal solution set S, and remove all the points in Y covered by [yi , yi + 1]. Repeat the above procedure, finally output S while Y becomes empty. We next show that S is an optimal solution. We claim that there is an optimal solution which contains the unit-length interval [y1, y1+ 1]. Suppose that there exists an optimal solution S such that y1 is covered by [x , x+1] S where x < 1. Since y1 is the leftmost element of the given set, there is no other point lying in [x , y1). Therefore, if we replace [x , x +1] in S by [y1, y1 +1], we will get another optimal solution. This proves the claim and thus explains the greedy choice property. Therefore, by solving the remaining subproblem after removing all the points lying in [y1, y1 + 1], that is, to find an optimal set of intervals, denoted as S , which cover the points to the right of y1 + 1, we will get an optimal solution to the original problem by taking union of [y1, y1 + 1] and S . The running time of our algorithm is O(n log n + n) = O(n log n), where O(n log n) is the time for soring and O(n) is the time for the linear scan.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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