题目
文章目录
题目大意和思路：AC代码：
题目大意和思路：
这道题，其实就是经典的贪心问题——区间覆盖，我当时被迷惑了。就是找多少个两两不相交的区间。 按照结束位置先后排个序就行 有不懂的欢迎留言
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;
}
