区间覆盖

题目连接：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]。

本题算法过程如下：

1. 将每个区间按照左端点从小到大进行排序。
2. 从前往后枚举区间，选择覆盖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;
}