1.区间问题

AcWing 905.区间选点

实现思路：

  1. 将每个区间按照右端点从小到大排序
  2. 从前往后依次枚举每个区间
    • 若当前区间中已经包含点，则跳过
    • 否则(即当前区间的左端点大于该点)，选择当前区间的右端点

证明：比较最终结果ans和选出的点个数cnt大小关系，即证ans>=cnt&&cnt>=ans。

先证ans<=cnt：由于上述方法选择的方案保证了每一个区间都至少包含一个点，因此为一个合法的方案，而ans表示的是合法方案中的最少点个数，因此ans<=cnt。

再证ans>=cnt:考虑没有被跳过的区间，区间互不相交，因此选中cnt个区间，要想覆盖所有区间，最终的答案一定至少为cnt个点（因为区间是独立的），即ans>=cnt。得证。

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;

//使用一个结构体来表示区间
struct Range{
    int l,r;
    //重载一下比较符号 方便后续按照区间的右端点排序
    bool operator< (const Range &W)const{
        return r<W.r;
    }
}range[N];
int n;

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    
    sort(range,range+n);//使用sort按右端点对区间排序
    
    int res=0,st=-2e9;//st表示枚举的点
    for(int i=0;i<n;i++)
        if(range[i].l>st){//若区间的左端点大于当前点 即不包含该点
            st=range[i].r;//赋为右端点
            res++;
        }
    
    cout<<res;
    return 0;
    
}

AcWing 908.最大不相交区间数量

实现思路：与上题思路一致，代码也一样

证明：比较最终结果ans和选出的区间个数cnt大小关系，即证ans>=cnt&&cnt>=ans。

先证ans>=cnt:由于选出的区间各不相交，因此为合法的方案，而ans为所有合法方案中最大的一个，因此有ans>=cnt。

再证ans<=cnt：运用反证法，假设ans>cnt，cnt表明每个区间都至少有一个选好的点，而ans表示所有不相交的区间的数量，说明至少应该有ans个点才能使每一个区间都有一个点，产生矛盾，因此ans<=cnt

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
strucy Range{
    int l,r;
    bool operator<(const Range &W)const{
        return r<W.r;
    }
}range[N];

int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    
    sort(range,range+n);
    
    int res=0,st=-2e9;
    for(int i=0;i<n;i++)
        if(range[i].l>st){
            st=range[i].r;
            res++;
        }
    cout<<res;
    return 0;
}

AcWing 906.区间分组

实现思路：

  1. 将所有区间按照左端点从小到大排序
  2. 从前往后处理每个区间
    • 判断能否将当前区间放到某个现有的组当中：判断现有组中的最后一个区间的右端点(即最大右端点)，是否小于当前区间的左端点，若小于，则意味着该组存在一个区间与当前区间相交，则不能放到该组，需要重新开一个组，否则可以加入当前组。
  3. 使用一个小根堆来存储所有组的右端点，那么堆顶就是右端点最小的一个组，如果当前区间的左端点小于这个组的右端点，就表示当前区间会与现有组产生相交，必然要新开一个组即加入堆中。否则当前区间至少可以加入堆顶的那个组，更新一下右端点（就是删除堆顶元素，再添加）。
  4. 最后输出堆的大小即为最小组数
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
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N=100010;

//使用一个结构体来表示区间
struct Range{
    int l,r;
    //重载一下 后续按照区间的左端点排序
    bool operator< (const Range &W)const{
        return l<W.l;
    }
}range[N];
int n;

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    
    sort(range,range+n);//使用sort按左端点对区间排序
    
    //使用优先队列构造小根堆
    priority_queue<int,vector<int>,greater<int> > heap;
    for(int i=0;i<n;i++){
        if(heap.empty() || heap.top()>=range[i].l) heap.push(range[i].r);//新开一个组
        else{//否则可以加入堆顶的组 更新一下右端点
            heap.pop();
            heap.push(range[i].r);
        }
    }
    
    cout<<heap.size();
    return 0;
    
}

AcWing 907.区间覆盖

实现思路：

设线段的左端点为start，右端点为end

  1. 将所有区间按照左端点从小到大排序
  2. 从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择一个右端点最大的区间，随后，将start更新为选中区间的右端点。当start >= end，结束
  3. 用双指针算法来找左端点<start，且右端点最大的区间，若找到的右端点依旧小于start，即无解；否则区间数量+1，且更新start

注意：一轮过后i=j-1，j是满足条件的区间，为了避免一些不必要的i枚举，所以i可以跳到满足条件的区间继续向后，但因为一轮后i++，所以先-1，下一轮就从j开始，这样又不会缺少或跳过满足的区间

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
56
57
58
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;

//使用一个结构体来表示区间
struct Range{
    int l,r;
    //重载一下 后续按照区间的左端点排序
    bool operator< (const Range &W)const{
        return l<W.l;
    }
}range[N];

int n;

int main(){
    int st,ed;//线段的起点和终点
    cin>>st>>ed;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    sort(range,range+n);
    int res=0;
    
    bool success=false;//设置一个bool表示是否有解
    
    for(int i=0;i<n;i++){//先枚举每个区间
        int j=i,r=-2e9;//j找左端点小于等于start且右端点最大的区间 r表示这个最大右端点
        
        while(j<n && range[j].l<=st){
            r=max(r,range[j].r);
            j++;//后移继续找
        }
        
        //找到满足条件的区间
        if(r<st) break;//如果最大右端点还是小于线段起点 则无解
        //有解
        res++;// 区间数+1
        
        if(r>=ed){//找到的当前区间已经完全包含线段了 直接退出
            success=true;
            break;
        }
        
        //继续找下一个满足区间
        st=r;//更新起点
        
        i=j-1;//因为i一轮后++ 所以要先当前区间-1 下一次就从区间j开始 
    }
    if(success) cout<<res;
    else cout<<-1;
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。