核心:贪心
- 按左端点排序
- 如果当前区间的左端点大于之前的区间的右端点,这个是一个新的区间
- 否则右端点=max(之前区间的右端点,当前的右端点)
#include<bits/stdc++.h>
using namespace std;
int n;
typedef pair<int,int> pii;
vector<pii> w;
vector<pii> res;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int st,ed;
cin>>st>>ed;
w.push_back({st,ed});
}
sort(w.begin(),w.end());
int cnt=1;
res.push_back({w[0].first,w[0].second});
for(int i=1;i<w.size();i++)
{
if(w[i].first>res.back().second)
{
res.push_back({w[i].first,w[i].second});
cnt++;
}
else res.back().second=max(w[i].second,res.back().second);
}
cout<<cnt<<endl;
// for(auto r:res)
// {
// cout<<r.first<<" "<<r.second<<endl;
// }
}