Activity Selection Problem

This problem can be solved using the Greedy Approach.

Goal: Given n activities with their start and finish times, find the maximum number of activities that a single person can perform, given that he/she can perform only one activity at a time.

For example:

ACTIVITY	A1	A2	A3
START	12	10	20
FINISH	25	20	30

Solution: A2, A3

Algorithm:

1. Sort the activities according to their finish times

2. Print the first activity in the sorted array

3. For the rest of the activities in the array: print the activity if its start time is greater than or equal to the finish time of the previous task

In the above example:

Sorting according to finish times:

ACTIVITY	A2	A1	A3
START	10	12	20
FINISH	20	25	30

Now print A2.

Then, check if A1 has start time >= finish time of A2. It doesn't. So, check the same for A3.

Since A3 has start time >= finish time of A2, print A3.

Output: A2, A3

Time Complexity: O(n) for sorted input, O(nlgn) for unsorted input.