> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/greedy-algorithms/1.activity-selection.md).

# 1.Activity Selection

Given **N activities with their start and finish times**. Select the **maximum number of activities** that can be performed by a **single person**, assuming that a person can **only work on a single activity** at a time.

**Note : The start time and end time of two activities may coincide.**

**Example 1:**

```
Input:
N = 5
start[] = {1,3,2,5,8,5}
end[] = {2,4,6,7,9,9}
Output: 4
Explanation:Perform the activites 1,2,4,5
```

**Example 2:**

```
Input:
N = 4
start[] = {1,3,2,5}
end[] = {2,4,3,6}
Output: 4
Explanation:Perform the activities1,3,2,4
```

## Solution: 

**Approach:**\
**Sort the array on basis of ending time**\
**Select from the first and check if a activity coincides or not** 

```cpp
bool comparator(pair<int, int> a, pair<int, int> b)
{

    return a.second < b.second;
}

int activitySelection(int start[], int end[], int n)
{

    vector<pair<int, int>> v;

    for (int i = 0; i < n; i++)
    {
        v.push_back({start[i], end[i]});
    }

    sort(v.begin(), v.end(), comparator);

    int act = 0;
    int count = 1;
    for (int i = 1; i < v.size(); i++)
    {
        if (v[i].first >= v[act].second)
        {
            act = i;
            count++;
        }
    }

    return count;
}
```

**Time Complexity: O(N log N)**