Activity Selection Problem

 Given N activities with their start and finish day given in array start[ ] and end[ ]. 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 given day.

Note : Duration of the activity includes both starting and ending day.

Example 1:

Input:
N = 2
start[] = {2, 1}
end[] = {2, 2}
Output: 
1
Explanation:
A person can perform only one of the
given activities.
ie.1-2

Example 2:

Input:
N = 4
start[] = {1, 3, 2, 5}
end[] = {2, 4, 3, 6}
Output: 
3
Explanation:
A person can perform 3 activities ie. 1-2,3-4,5-6.

Example 3:

Input:
N = 6
S[] = {1,3,0,5,8,5}
F[] = {2,4,6,7,9,9}
Output: 
4
Explanation:
a person can perform 4 activities 
ie. 1-2,3-4,5-7,8-9 

method : greedy approach

1) push the start and finish time of the activities in a vector and sort the vector according to their finishing time 
2) Select the first activity from the sorted array and set counter to 1
3) now traverse the whole vector starting from index 1, If the start time of this activity is greater than the finish time of the previously selected activity then increment the counter
4)return the counter

c++ implementation:

int activitySelection(vector<int> s, vector<int> e, int n)
    {
        vector<pair<int,int>>v;
  
        for(int i=0;i<n;i++)
        v.push_back(make_pair(e[i],s[i]));
        
        sort(v.begin(),v.end());
        
        int c=1; int m=v[0].first;
        for(int i=1;i<n;i++)
        {
            if(v[i].second>m)
            {
                c++;
                m=v[i].first;
            }
            
        }
        
        
        return c;
    }

Time Complexity: O(nlogn) 

space Complexity: O(n)