Using C++

and the following

The procedure GREEDY-ACTIVITY-SELECTOR is an iterative version of the procedure RECURSIVE-ACTIVITY-SELECTOR. It also assumes that the input activities are ordered by monotonically increasing finish time. It collects selected activities into a set A and returns this set when it is done.

GREEDY-ACTIVITY-SELECTOR (s, f )

1 n = s.length

2 A = [{a1 }

3 k = 1

4 for m = 2 to n

5 if s[m] >= f [k]

6 A = A Union {am}

7 k = m

8 return A

Activity Selection Last-to-Start Implementation:

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. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

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.

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