目录

• 前言
• 区间选点
• • Code
• 最大不相交区间数量
• • Code
• 区间分组
• • Code
• 区间覆盖
• • Code

前言

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

区间选点

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

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

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

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

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

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

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109−10^9≤a_i≤b_i≤10^9−109≤ai​≤bi​≤109

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

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

Code

#include 
#include 
#define l first
#define r second
using namespace std;
typedef pair 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;
}

最大不相交区间数量

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

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

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

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

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

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109−10^9≤a_i≤b_i≤10^9−109≤ai​≤bi​≤109

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

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

Code

#include 
#include 
#include 
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;
}

区间分组

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

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

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

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

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109−10^9≤a_i≤b_i≤10^9−109≤ai​≤bi​≤109

输入样例：

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)的，而在每个区间下遍历每个组又是O(n)O(n)O(n)的，所以复杂度就是O(n2)O(n^2)O(n2)的，显然对于10510^5105的数据量是会超时的，所以不妨使用小根堆优化找合适的组这一步，这样一来复杂度就优化至了O(nlogn)O(nlogn)O(nlogn)了。

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

Code

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
#define l first
#define r secondconst int N = 1e5 + 10;PII ran[N];
priority_queue, greater> 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;
}

区间覆盖

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

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

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

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

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

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

如果无解，则输出 −1。

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109,−10^9≤a_i≤b_i≤10^9,−109≤ai​≤bi​≤109,
−109≤s≤t≤109−10^9≤s≤t≤10^9−109≤s≤t≤109

输入样例：

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 
#include 
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;
}