Activity selection problem

#1

hi, i solved this question by first sorting the pairs and then finding out the pairs which cannot be selected by comparing the pairs
here is the code
#include
#include
using namespace std;
int main() {
int t;
cin>>t;
for(int k=0;k<t;k++)
{
int n;
cin>>n;
pair<int,int> p[n];
for(int i=0;i<n;i++)
{
int f,s;
cin>>f>>s;
p[i]=make_pair(f,s);
}
sort(p,p+n);
int count=0;
// for(int i=0;i<n;i++)
// {
// cout<<p[i].first<<" “<<p[i].second<<endl;
// }
for(int i=1;i<n;i++)
{
int c1=p[i].first,c2=p[i].second;
if(p[i-1].first<c1 && c1<p[i-1].second)
count++;
}
// cout<<count<<” ";
cout<<n-count<<endl;
}
return 0;
}

#2

hi @gurkirat2600
A basic activity selection problem which uses Greedy approach. The implementation mentioned here states to sort the activities in the increasing order of their finishing times. Initially, we choose the first activity. Now, starting from second activity, current activity can be selected if the finish time of previous selected activity is less than or equal to the starting time of current activity

#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int main(int argc, char const *argv[])
{
    int t;
    cin>>t;
    while(t--) {
        int n, a, b;
        cin>>n;
        pair<int, int> arr[n];
        for(int i=0;i<n;i++) {
            cin>>a>>b;
            arr[i] = make_pair(a, b);
        }
        sort(arr, arr+n, cmp);
        // for(int i=0;i<n;i++) {
        //  cout<<arr[i].first<<" "<<arr[i].second<<endl;
        // }
        int ans = 1, chosen = 0;
        for(int i=1;i<n;i++) {
            if(arr[i].first>=arr[chosen].second) {
                ans++;
                chosen = i;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.