# 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**:

- Sort the activities according to their
**finish**times - Print the first activity in the sorted array
- 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.