文章
16
粉丝
0
获赞
43
访问
2.7k
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int,int>> segs;
for(int i = 0;i < n;++i)
{
int a,b;
cin >> a >> b;
segs.push_back(make_pair(a,b));
}
sort(segs.begin(),segs.end());
vector<pair<int,int>> ans;
ans.push_back(segs[0]);
int res = 0;
for(int i = 1;i < n;++i)
{
// 注意这里是引用,不加引用会导致更改无法应用到原数组内
auto& last = ans.back();
// 如果第一个区间完全覆盖了第二个区间,代表这个大区间必须去掉,将小区间留下
if(segs[i].first > last.first && segs[i].second < last.second)
{
last = segs[i];
res++;
}
// 阶梯式,正常将后面覆盖的区间去掉
else if(segs[i].first < last.second)
{
res++;
}
else
{
ans.push_back(segs[i]);
}
}
cout << res << endl;
return 0;
}
经典区间模型,区别是排序后统计区间时,如果前者区间完全覆盖了后者(前者区间头小于后者区间头,前者区间尾大于后者区间尾),那就要把前者区间去掉而保留后者,因为如果留下前面的大区间,可能会导致后面的区间仍旧有覆盖,不是最少移除区间数量(有一点贪心思想在里面)
登录后发布评论
暂无评论,来抢沙发