---

前言

贪心真是玄学，规律全靠猜，证实靠样例！

---

区间选点

给定 $N$ 个闭区间 $[a_i,b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数 $N$，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
$1\le N\le 10^5,$
$-10^9\le a_i\le b_i\le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

---

思路：对于所有区间按照右端点进行一遍sort，然后从第一个区间开始，选择右端点作为那个要包含的其中一个点choice，因为这个choice很有希望能处在往后面几个区间的范围里，这样就减少了要选择点的次数，如果遇到某个区间使得choice不在其里面，那就更新一下choice为当前这个区间的右端点，同时点的个数+ 1，按照这个步骤循环往复遍历所有区间… …

Code

#include <iostream>
#include <algorithm>
#define l first
#define r second
using namespace std;
typedef pair<int, int> PII;const int N = 1e5 + 10;PII R[N];
int n, choice, ans = 1;bool cmp(PII a, PII b){return a.r < b.r;
}int main(){scanf("%d", &n);for(int i = 0;i < n;i ++){int a, b;scanf("%d %d", &a, &b);R[i] = {a, b};}sort(R, R + n, cmp);        //每个区间按照右端点排序/*如果将每个区间的右端点作为被选中的那个点  那么对于后面的区间来讲，再需要新增的点的频率可能会降低首先选择第一个区间右端点*/choice = R[0].r;        for(int i = 1;i < n;i ++){if(R[i].l <= choice && choice <= R[i].r)            continue;       //这个区间被“照顾”到了  可以不用管了choice = R[i].r;        //这个区间跟前面的没有交集了  要更新右端点ans ++ ;        //多选择一个点}cout << ans << endl;return 0;
}

---

最大不相交区间数量

给定 $N$ 个闭区间 $[a_i,b_i]$，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

输入格式
第一行包含整数 $N$，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
$1\le N\le 10^5,$
$-10^9\le a_i\le b_i\le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

---

关于这道题，其实在以前有一个很实际的例子介绍过：洛谷 P1803 - 凌乱的yyy / 线段覆盖。
那么仍然是右端点sort一遍，然后挨着找最多的不相交区间数量，其实可以注意到跟上题思路虽说不一样，但最终带来的结果却是一样的，因此完全可以用同样的代码（下面微调整了一下）。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 1e5 + 10;struct ran{int l, r;bool operator< (const ran &t)const{return r < t.r;}
}Range[N];int n, ed;int main(){cin >> n;for(int i = 0;i < n;i ++){int a, b;cin >> a >> b;Range[i] = {a, b};}sort(Range, Range + n);int ans = 0, ed = -2e9;for(int i = 0;i < n;i ++)if(ed < Range[i].l){ans ++;ed = Range[i].r;}cout << ans << endl;return 0;
}

---

区间分组

给定 $N$ 个闭区间 $[a_i,b_i]$，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输入格式
第一行包含整数 $N$，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
$1\le N\le 10^5,$
$-10^9\le a_i\le b_i\le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

---

思路：按照左端点从小到大sort一遍，然后每组记录一个当前组内所有区间里最大的那个右端点值Max_r，方便后面的区间判断适不适合加入到这个组里来。也就是

• 遍历每个区间，如果有某个组的Max_r < Range[i].l，说明该区间可以加到里面去，因此更新一下这个组的Max_r为Range[i].r意味着已经加入了。
• 由于可能有很多组都满足上面那个条件，只需任选一组就可以。
• 如果不存在满足上面条件的组，那就需要为该区间“另起炉灶”新开一个组。

注意到：遍历每个区间是$O(n)$的，而在每个区间下遍历每个组又是$O(n)$的，所以复杂度就是$O(n^2)$的，显然对于$10^5$的数据量是会超时的，所以不妨使用小根堆优化找合适的组这一步，这样一来复杂度就优化至了$O(nlogn)$了。

• 使小根堆存各个组的Max_r，取堆顶，如果最小的Max_r都不能满足Max_r < Range[i].l那就没有可以满足的了，直接“另起炉灶”；如果堆顶可以满足条件，那就放到堆顶这一组里。总而言之都能一步到位。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
#define l first
#define r secondconst int N = 1e5 + 10;PII ran[N];
priority_queue<int, vector<int>, greater<int>> heap;       //用小根堆存下每个组的Max_r
int n;int main(){cin >> n;for(int i = 0;i < n;i ++){int u, v;cin >> u >> v;ran[i] = {u, v};}sort(ran, ran + n);for(int i = 0;i < n;i ++){if(heap.empty())        heap.push(ran[i].r);else{int tt = heap.top();if(tt < ran[i].l){heap.pop();heap.push(ran[i].r);        //变相改变这个组的Max_r}else        heap.push(ran[i].r);}}cout << heap.size() << endl;return 0;
}

---

区间覆盖

给定 $N$ 个闭区间 $[a_i,b_i]$ 以及一个线段区间 $[s,t]$，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 −1。

输入格式
第一行包含两个整数 $s$ 和 $t$，表示给定线段区间的两个端点。

第二行包含整数 $N$，表示给定区间数。

接下来 $N$ 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需最少区间数。

如果无解，则输出 −1。

数据范围
$1\le N\le 10^5,$
$-10^9\le a_i\le b_i\le 10^9,$
$-10^9\le s\le t\le 10^9$

输入样例：

1 5
3
-1 3
2 4
3 5

输出样例：

2

---

思路：按照左端点对区间sort一遍，然后

1. 对于每个能包含住s（左限制端点）的区间，找到那个有最大r的区间，然后让这个r成为新的s（言外之意原来那个s已经被“照顾”了，现在的r才是新的需要考虑照顾的左限制端点），并让区间数ans ++。
2. 如果发现找到的r >= t，说明已经把整个要求的限制区间都囊括到了，break。
3. 如果发现找到的r < s，说明连左限制端点都囊括不到，答案不存在，break。
4. 下一次要关注的区间直接是有最大r的区间，并重复步骤1。

Code

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5 + 10;struct Range{int l, r;bool operator < (const Range &t) const{return l < t.l;}
}ran[N];
int n, s, t;int main(){cin >> s >> t;cin >> n;for(int i = 0;i < n;i ++){int a, b;cin >> a >> b;ran[i] = {a, b};}sort(ran, ran + n);int ans = 0;bool flag = false;for(int i = 0;i < n;i ++){int ed = -2e9;      //ed作为找到的最大那个rint j = i;while(j < n && ran[j].l <= s){      //双指针寻找最大red = max(ed, ran[j].r);j ++;}if(ed < s){        //最大的右端点也不能包含到点s        注意用“<”因为可能s 等于 tbreak;}ans ++;i = -- j;          //循环跳转， -- j是因为上面while执行了一遍多余的j ++s = ed;if(ed >= t){flag = true;break;}}if(flag)        cout << ans << endl;else            cout << -1 << endl;return 0;
}