➤ Problem Link : BUSYMAN
👉 Hint : Use sorting and think of a greedy approach
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool comp(pair<ll,ll> a,pair<ll,ll> b)
{
if(a.second != b.second)
return a.second<b.second;
return a.first<b.first;
}
int main()
{
int t;
cin>>t;
vector<pair<ll,ll> > v;
while(t--)
{
ll n,s,e;
ll ans=0;
cin>>n;
v.clear();
while(n--)
{
cin>>s>>e;
v.push_back(make_pair(s,e));
}
sort(v.begin(),v.end(),comp);
ll curr=-1;
for(auto it=v.begin();it!=v.end();it++)
{
if(it->first>=curr)
{
curr=it->second;
ans++;
}
}
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.