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

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)