> For the complete documentation index, see [llms.txt](https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/chapter1/activity-selection-problem.md).

# 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.