AcWing907. 区间覆盖

参考的视频讲解：↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
【贪心算法08-区间问题03-区间覆盖】
每次贪心就是选择左端点里面＜起始端点里面右边界最大的，这样就是保证了最少区间个数!
然后每次迭代都会更新一次起始端点st，反复运用本算法。
一定要仔细看视频讲解！！！

#include<iostream>
#include<algorithm>
#define N 100010
#define INF 2e9
using namespace std;
int n ;
struct Range{int l, r;bool operator<(const Range& r1){return l < r1.l;}
}range[N];
int main(){int st , ed;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);int res = 0 ;bool success = false;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){res = -1;//如果挑出来的最大右端点小于起始端点，那么无解，返回-1break;}++res;if(r >= ed){//如果右边界已经可以超过末尾端点ed，那么求解完毕，返回ressuccess = true;break;}st = r;i = j - 1;}if (!success) res = -1;printf("%d\n", res);
}