区间覆盖

题目 区间覆盖

image-3e96944d

思路分析

要用多个区间去覆盖掉一个大区间 要求数量最少

那么贪心告诉我们 每个小区间要取得越大越好

但是某个区间能不能选 在于它的左端点是否小于st位置

那么问题就转换成了 在保证所有左端点小于st的区间中 选其中右端点往右延伸最长的

image-f9aa8b3e

所以

把所有区间按左端点进行排序

然后从前往后枚举每个区间 在所有能覆盖st的区间中 选择右端点最靠右的区间 然后把st更新成右端点的最大值

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

struct Range{

    int l,r;

    bool operator<(const Range& other)const{

        return l<other.l;

    }

}ranges[N];

int n;

int st,ed;

int main()

{

    cin>>st>>ed;

    cin>>n;

    for(int i=0;i<n;i++){

        cin>>ranges[i].l>>ranges[i].r;

    }

    sort(ranges,ranges+n);

    int cnt=0;

    bool success=false;

    for(int i=0;i<n;i++){

        int r=-2e9;

        int j=i;

        while(j<n && ranges[j].l<=st){

            r=max(r,ranges[j].r);

            j++;

        }

        if(r<st){

            cnt=-1;

            break;

        }

        cnt++;

        if(r>=ed){

            success=true;

            break;

        }

        st=r;

        i=j-1;//for循环里有个i++ 防止跳过区间 把它置成j-1

    }

    if(!success)

        cnt=-1;

    cout<<cnt;

    return 0;

}

同类题型

视频讲解

⬅️ 区间模型 🏠 00-刷题理模型 ➡️ 区间选点