贪心问题———区间覆盖
输入样例：
1 5
3
-1 3
2 4
3 5输出样例：
2分析：
我们根据贪心的思路，能覆盖更大的范围就意味着能用更少的区间段
我们将线段从左端点进行排序
代码演示：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,st,ed;
// 定义结构体
struct Range
{
int l,r;
// 排序要用到重载运算符
bool operator< (const Range &W)const
{
return l<W.l;
}
}range[N];
int main(void)
{
cin >>st >> ed;
cin >> n;
for(int i=0;i<n;i++)
{
int l,r;
cin >> l >> r;
range[i]= {l,r};
}
sort(range,range+n);
bool flag= false;
int res = 0;
for(int i=0;i<n;i++)
{
int j=i,r = -2e9;
while(j<n&&range[j].l<st)
{
// 这里寻找更长的线段
r = max(r,range[j].r);
j++;
}
if(r<st)
{
// 显然不合法
flag = false;
break;
}
res++;
if(r>=ed)
{
flag = true;
break;
}
// 一轮循环后，若还没找到，将st定为当前线段最右边的点
st = r;
i = j-1;
}
if(!flag) cout <<"-1" << endl;
else cout <<res << endl;
return 0;
}感谢查看！