Consider a greedy strategy for the following problem: We have a company with n w
ID: 3861735 • Letter: C
Question
Consider a greedy strategy for the following problem: We have a company with n workers. Worker w_i works a shift (s_i, f_i), where s_i is that worker's start time and f_i the finish time. We want to form a small committee C subset {w_1, ..., w_n} with the following property: for every worker w_i there exists a worker w_c elementof C such that the shift of w_i overlaps with the shift of w_c. That is, the intervals (s_i, f_i) and (s_c, f_c) must intersect. So the problem here is to find the smallest possible set C of workers whose shifts overlap with all workers. (a) Describe the greedy choice. ("Choose the first worker with property P.") (b) Show that if there is an optimal solution for which the greedy choice was not made, then an exchange can be made to conform with your greedy choice. ("Let schedule S use worker w_j who does not satisfy property P, and let w_k be the worker that does. Here I show that the schedule S', which is obtained by exchanging worker w_j for w_k, is just as good as S ...") (c) Describe, in English, how to implement a greedy algorithm. (d) How long would your algorithm take?Explanation / Answer
The following is the greedy approach that finds the minimum cover in O(nlogn) time. The input is a set of the intervals sorted based on their start times. So, we now know that lower bound is O(nlogn) because of sorting. The only significant step that we should be analysis is the step 5. We can also prove that the upper bound will be O(nlogn).
FindMinTilingCover(Interval I)
1. Initialize Ymin = {} // It holds Tiling intervals
2. x = I.start // start of Interval I
3. y = I.end // end of Interval I
4. while (x < y)
5. i = Among all the intervals that has started before x, pick the one that the farthest right end point
6. Ymin = Ymin U {i}
7. x = i.end
The algorithm reduces the search space into smaller region, every time we update the value of x, and thus it has the optimal sub structure. Suppose that T is not an optimal solution, and there exist an optimal solution S, such that S has an interval selected, which doesn't have the farthest right end point. Now, if we note carefully, we can easily replace that interval with the one that has the farthest right end point and the final set will be more efficient. Thus we have proved that this greedy algorithm always works and gets the optimal solution.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.