Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible will all previously selected activities.

Use any language you choose to implement the activity selection last-to-start algorithm described above. Include a verbal description of your algorithm, pseudocode and analysis of the theoretical running time. You do not need to collected experimental running times. The 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.

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:

**Note: There is an alternative optimal solution for Set 1. Since activities 8 and 9 have the same start time of 8, a2 a4 a8 a11 would be an alternative solution. Your program only needs to find one of the optimal solutions. For either solution the activities differ from the solution presented in the text which uses the earliest-finish time criteria.

The procedure GREEDY-ACTIVITY-SELECTOR is an iterative version of the pro- cedure REcURSIVE-ACTIVITY-SELECTOR. It also assumes that the input activi- ties are ordered by monotonically increasing finish time. It collects selected actv- ities into a set A and returns this set when it is done. GREEDY-ACTIVITY-SELECTOR (s. f) 1 n=s.length 4 for m=2to n A = AU(an) 7 8 return A The procedure works as follows. The variable k indexes the most recent addition to A, corresponding to the activity ak in the recursive version. Since we consider the activities in order of monotonically increasing finish time, jk is always the maximum fnish time of any activity in A. That is. (16.3) The procedure GREEDY-ACTIVITY-SELECTOR is an iterative version of the pro- cedure REcURSIVE-ACTIVITY-SELECTOR. It also assumes that the input activi- ties are ordered by monotonically increasing finish time. It collects selected actv- ities into a set A and returns this set when it is done. GREEDY-ACTIVITY-SELECTOR (s. f) 1 n=s.length 4 for m=2to n A = AU(an) 7 8 return A The procedure works as follows. The variable k indexes the most recent addition to A, corresponding to the activity ak in the recursive version. Since we consider the activities in order of monotonically increasing finish time, jk is always the maximum fnish time of any activity in A. That is. (16.3)