✅Activity Selection (Contest)

Activity Selection easy Time Limit: 2 sec Memory Limit: 128000 kB

Problem Statement :

You are given N activities with their start and finish times as S and F. Find 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. Input The first line of input contains one integer denoting N. Next N lines contain two space-separated integers denoting the start time and finish time for the ith activity.

Constraints 1 ≤ N ≤ 10^6 1 ≤ S[i] <= F[i] ≤ 10^9 Output Output one integer, the maximum number of activities that can be performed Example Sample Input 6 1 2 3 4 1 6 5 7 8 9 5 9

Sample Output 4

Explanation:- He can perform activity 1 2 4 5

Sample Input:- 4 4 6 5 6 3 5 6 8

Sample Output:- 2

link: https://my.newtonschool.co/playground/code/c2ibdvytn926/

#include <bits/stdc++.h> // header file includes every Standard library
#define ll  long long
#define pb  push_back
#define endl '\n'
#define pi  pair<int,int>
#define ci  vector<int>
#define all(a)  (a).befin(),(a).end()
#define fi first
#define se second
#define sz(x) (int)x.size()
#define hell 1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define dep(i,a,b)  for( i=a;i>=b;i--)
#define lbnd  lower_bound
#define ubnd  upper_bound
#define bs    binary_search
#define mp  make_pair
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
const int inf=1e9+9;
pi a[N];
int dp[N];
map<int,int> m;
vector<int> v[N];
void solve(){
    int n; cin >>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].fi >>a[i].se;
        m[a[i].fi]=m[a[i].se]=1;
    }
    int p=1;
    for(auto &i:m){
        i.se +=p;
        p=i.se;
    }
    for(int i=1;i<=n;i++){
        a[i].fi=m[a[i].fi];
        a[i].se=m[a[i].se];
        v[a[i].se].push_back(a[i].fi);
    }
    for(int i=1;i<N;i++){
        dp[i]=dp[i-1];
        for(auto j:v[i])
                dp[i]=max(dp[i],1+dp[j-1]);
    }
    cout << dp[N-2];

}
void  testcases(){
    int tt=1;
    while(tt--){
        solve();
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t start=clock();
    testcases();
}