Python | Greedy Algorithm Program

Implement the activity selection last-to-start algorithm described above in python. Include a verbal description of your algorithm, pseudocode and analysis of the theoretical running time.

This program should read input from a file named act.txt. The file contains lists of activity sets with number of activities in the set in the first line followed by lines containing the activity number, start time & finish time. Example act.txt: 11 1 1 4 2 3 5 3 0 6 4 5 7 5 3 9 6 5 9 7 6 10 8 8 11 9 8 12 10 2 14 11 12 16 3 3 6 8 1 7 9 2 1 2

In the above example the first activity set contains 11 activities with activity 1 starting at time 1 and finishing at time 4, activity 2 starting at time 3 and finishing at time 5, etc.. The second activity set contains 3 activities with activity 3 starting at time 6 and finishing at time 8 etc. The activities in the file are not in any sorted order. Your results including the number of activities selected and their order should be outputted to the terminal. For the above example the results are:

Set 1 Number of activities selected = 4 Activities: 2 4 9 11 Set 2 Number of activities selected = 2 Activities: 2 1

Suppose s 3(a1, a2, ,an} is a set of activities and each ai = [Si, f). 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. Thus, it will become the same if the time is running in reverse and the optimal solution is produced. Since, the best-looking choice is considered so it is greedy. The following is the algorithm that finds optimal solution by selecting last activity to start: Proposed Algorithm GREEDY-ACTIVITY-SELECTOR (s 1, n=s.length 2, A={an} 3, k = n 4, for m= n-1 down to 1 7. k=m 8. return A Suppose s 3(a1, a2, ,an} is a set of activities and each ai = [Si, f). 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. Thus, it will become the same if the time is running in reverse and the optimal solution is produced. Since, the best-looking choice is considered so it is greedy. The following is the algorithm that finds optimal solution by selecting last activity to start: Proposed Algorithm GREEDY-ACTIVITY-SELECTOR (s 1, n=s.length 2, A={an} 3, k = n 4, for m= n-1 down to 1 7. k=m 8. return A