Activity Selection Problem Analysis

Definition: Scheduling a resource among several competing activities.
Goal: To select a maximum-size set of mutually compatible activities.

For example consider the following problem:

Rules to Select the items are:
1. Sort the activities according to thier finish time.
2. Select the first item from the Sorted list.
3. Then for rest of the activities select the items if
    Start Time of the current activity > = Finish Time of the previous activity.

So if we sort the activities according to their finish time (rule 1) it becomes like below:

 Now for the first item select the first activity from above list (rule 2). So, activity A1.

Now the current activity is A2 and its Start time 3 > = finish time of prevoius activity is 2. So, A2 is also selected.

Now the current activity is A1 and its Start time 0 < = finish time of prevoius activity is 4.  So, A1 is will not be selected.

Now the current activity is A5 and its Start time 5 > = finish time of prevoius activity is 4 (last selected item). So, A5 is also selected.

Now the current activity is A4 and its Start time 5 < = finish time of prevoius activity is 7 (last selected item). So, A4 will not be selected.

Now the current activity is A6 and its Start time 8 > = finish time of prevoius activity is 7 (last selected item). So, A6 is also selected.

So, the selected activities will be:
A3 , A2, A5, A6

To see the python implementation of the above algorithm click here