题目大意和思路:
这道题,其实就是经典的贪心问题——区间覆盖,我当时被迷惑了。就是找多少个两两不相交的区间。
按照结束位置先后排个序就行
有不懂的欢迎留言
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e8+9;
struct node
{
int s;
int l;
}c[maxn];
bool cmp(node a,node b)
{
return a.l<b.l;
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>c[i].s>>c[i].l;
c[i].l = c[i].s + c[i].l;
}
sort(c,c+n,cmp);
int en = 0;
int st = 0;
en = c[0].l;
int cnt = 1;
for(int i=1;i<n;i++)
{
if(c[i].s>=en)
{
cnt++;
st = c[i].s;
en = c[i].l;
}
}
cout<<cnt<<endl;
return 0;
}