题目连接：https://www.acwing.com/problem/content/909/
题目描述
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
输入描述
第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。
第二行包含整数 N，表示给定区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出描述
输出一个整数，表示所需最少区间数。
如果无解，则输出 −1。
1≤N≤105
−109≤ai≤bi≤109
−109≤s≤t≤109
示例
输入
1 5
3
-1 3
2 4
3 5
输出
2
分析
算法过程
记待覆盖区间为[st,ed]。
本题算法过程如下：
- 将每个区间按照左端点从小到大进行排序。
- 从前往后枚举区间，选择覆盖st且右端点最大的区间，用该区间的右端点更新st，重复本步骤直到完成整个区间的覆盖。
证明
将该算法得到的结果与最优解进行对比。记算法的到的方案为A，最优解为B。
以第一个被选中的区间为例，A选出的区间的右端点一定大于等于B选出区间的右端点，因此可以用A的第一个区间替换B的第一个区间，B的正确性不变，区间数量不变，因此新B依然是最优解。
此时A与B第一个区间完全一样，重复上面的步骤对第二个、第三各区间····进行同样的操作替换最优解中的区间，即可在保持区间数量不变和正确性的前提下将最优解变为A。
证毕。这是局部最优解与全局最优解保持一致的典型贪心算法。
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int N = 1e5 + 10;
int n;
P a[N];
int st, ed;
int main()
{
cin >> st >> ed >> n;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
a[i].first = l;
a[i].second = r;
}
sort(a, a + n);
int res = 0;
bool success = false;
for (int i = 0; i < n; i++)
{
int j = i, r = -1e9 - 10;
while (j < n && a[j].first <= st)
{
r = max(r, a[j].second);
j++;
}
j--;
if (r < st)
{
res = -1;
break;
}
res++;
st = r;
if (r >= ed)
{
success = true;
break;
}
i = j;
}
if (success)
cout << res << endl;
else
cout << -1 << endl;
return 0;
}