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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/greedy-algorithms/1.activity-selection.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.