贪心：区间问题

---

前言

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

---

区间选点

给定 $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
1
2
3
4

输出样例：

2
1

---

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

Code

#include 
#include 
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

最大不相交区间数量

给定 $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
1
2
3
4

输出样例：

2
1

---

关于这道题，其实在以前有一个很实际的例子介绍过：洛谷 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

区间分组

给定 $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
1
2
3
4

输出样例：

2
1

---

思路：按照左端点从小到大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 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int, int> PII;
#define l first
#define r second

const 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

---

区间覆盖

给定 $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
1
2
3
4
5

输出样例：

2
1

---

思路：按照左端点对区间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作为找到的最大那个r
        
        int j = i;
        while(j < n && ran[j].l <= s){      //双指针寻找最大r
            ed = max(ed, ran[j].r);
            j ++;
        }
        
        if(ed < s){        //最大的右端点也不能包含到点s        注意用“<”因为可能s 等于 t
            break;
        }
        
        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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55