Re-write the answer to this question in your own words, but same answer. Problem
ID: 3586519 • Letter: R
Question
Re-write the answer to this question in your own words, but same answer.
Problem Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution Step-by-step solution Step 1 of 1 Suppose s { a1,a2 , an} is a set of activities and each ai-lsif). Consider that the activities are sorted by finish time. Now, the goal is to find the largest possible set of non-overlapping of activities by selecting the activities from ending instead selecting from beginning The following is the algorithm that finds optimal solution by selecting last activity to start: Proposed Algorithm GREEDY-ACTIVITY-SELECTOR (s.f) 1. n=s, length 2. A={an} 3, k=n 4. for m n-1 down to 1 7 8. return A . The above algorithm takes starting times and finishing times of activities as input. They are sorted by finish time . The algorithm initially selects last activity to start first. . Then the algorithm scans through the activities in descending order and finds a compatible activity to add it to set A Since, the above algorithm tries to find an optimal solution in each stage. This approach is obviously a greedy algorithm Optimal solution: Consider s is a sub set of ta, an, is an optimal solution obtained by the approach that selects the first activity to start s can also be obtained by the proposed approach. That is, the solution produced by the approach that selects first activity to start can also be obtained by the proposed approach Therefore, the proposed approach also produces an optimal solution.Explanation / Answer
Let an activity Ai is defined by its Start time Si and Finish time Fi as Ai = (Si,Fi).
Let n be the number of activities
Let A = {A1..An} be the set of n activities, sorted by finish time.
The algorithm has to find the largest subset of non-overlapping activities.
The algorithm will choose the last activity An (it finishes the last). Add it to the final set AF . Then, It will find the last activity whose finish time is lesser than the start time of An, by iterating the loop from n-1 down to 1.
Let that activity be Ak . S(Ak) is lesser than F(An). Add that activity Ak to final set AF .
Similarly, it will find the last activity whose finish time is lesser than start time of Ak .
All of this can be done in one iteration of the set activities. starting from n-1 to 1. and updating the value of K, every time a new activity is added to the final set.
since the above approach tries to find an optimal solution in each stage( by finding the last activity whose finish time is lesser than the start time of the previously selected activity), it is a greedy algorithm.
Consider S' is an optimal solution generated by choosing the activity that starts first. the same set can also be generated by the above-selected algorithm. Thus it is optimal as well.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.