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