算法学习系列（三十四）：区间问题（贪心）

大家好，欢迎来到IT知识分享网。

引言

这个区间问题其实是个贪心问题，说起这个贪心问题，其实没有什么套路模板可言，就是多做题，这道题你做过类似的，那么你就可以 $AC$ ，否则都是空谈。所以该篇主要还是以例题为主进行讲解。

一、区间选点

这个区间问题无外乎首先就是左端点排序、右端点排序、双关键字排序，至于什么时候怎么排序就得靠经验了。

思路：按照区间的右端点从小到大排序，接着访问每个区间，只要下一个区间左端点大于 $ed$ ，则 $res++$ ，然后将当前区间右端点的值赋给 $ed$

题目描述：

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N，表示区间数。 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。 输出格式 输出一个整数，表示所需的点的最小数量。 数据范围 1≤N≤105,−109≤ai≤bi≤109 输入样例： 3 -1 1 2 4 3 5 输出样例： 2 

示例代码：

#include <iostream> #include <algorithm> using namespace std; const int N = 1e5+10; int n; struct Seg { 
    int l, r; bool operator<(const Seg& other) { 
    return r < other.r; } }segs[N]; int main() { 
    scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d%d", &segs[i].l, &segs[i].r); sort(segs, segs+n); int res = 0, l = -2e9, r = -2e9; for(int i = 0; i < n; ++i) { 
    if(segs[i].l > r) { 
    res++; r = segs[i].r; } } printf("%d\n", res); return 0; } 

二、最大不相交区间数量

思路：这道题跟上道题是一模一样的，大家可以仔细思考下。

题目描述：

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。 输出可选取区间的最大数量。 输入格式 第一行包含整数 N，表示区间数。 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。 输出格式 输出一个整数，表示可选取区间的最大数量。 数据范围 1≤N≤105,−109≤ai≤bi≤109 输入样例： 3 -1 1 2 4 3 5 输出样例： 2 

示例代码：

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N = 1e5+10; int n; struct Seg { 
    int l, r; bool operator<(const Seg& other) { 
    return r < other.r; } }segs[N]; int main() { 
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; ++i) cin >> segs[i].l >> segs[i].r; sort(segs, segs+n); int res = 0, l = -2e9, r = -2e9; for(int i = 0; i < n; ++i) { 
    if(segs[i].l > r) { 
    res++; r = segs[i].r; } } cout << res << endl; return 0; } 

三、区间分组

这个区间问题无外乎首先就是左端点排序、右端点排序、双关键字排序，至于什么时候怎么排序就得靠经验了。

思路：按照左端点从小到大排序，遍历每一个区间，如果遇到当前区间的左端点小于等于在组中右端点最小的了，那么已经不能加入组中了，需要重新开辟一个组，否则把当前区间加到组中（还是右端点最小的组），更新右端点。这个组是拿小根堆抽象出来的，存的是这个组中的最右的点。

题目描述：

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。 输出最小组数。 输入格式 第一行包含整数 N，表示区间数。 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。 输出格式 输出一个整数，表示最小组数。 数据范围 1≤N≤105,−109≤ai≤bi≤109 输入样例： 3 -1 1 2 4 3 5 输出样例： 2 

示例代码：

#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int N = 1e5+10; int n; struct Seg { 
    int l, r; bool operator<(const Seg& other) { 
    return l < other.l; } }segs[N]; int main() { 
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; ++i) cin >> segs[i].l >> segs[i].r; sort(segs, segs+n); priority_queue<int, vector<int>, greater<int>> heap; for(int i = 0; i < n; ++i) { 
    if(heap.empty() || heap.top() >= segs[i].l) { 
    heap.push(segs[i].r); } else { 
    heap.pop(); heap.push(segs[i].r); } } cout << heap.size() << endl; return 0; } 

四、区间选点

思路：按左端点从小到大排序，遍历每个区间，每次取左端点 $<=start$ 的区间中右端点最大的，然后用右端点更新 $start$

题目描述：

给定 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 

示例代码：

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N = 1e5+10; int n; int start, ed; struct Seg { 
    int l, r; bool operator<(const Seg& other) { 
    return l < other.l; } }segs[N]; int main() { 
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> start >> ed; cin >> n; for(int i = 0; i < n; ++i) cin >> segs[i].l >> segs[i].r; sort(segs, segs+n); int res = 0; bool flag = false; for(int i = 0; i < n; ++i) { 
    int j = i, r = -2e9; while(j < n && segs[j].l <= start) { 
    r = max(r, segs[j].r); j++; } if(r < start) { 
    res = -1; break; } res++; if(r >= ed) { 
    flag = true; break; } start = r; i = j - 1; } if(!flag) res = -1; cout << res << endl; return 0; }