---
title: "区间覆盖"
created: 2025-11-28
tags:
  - 算法
---

# 区间覆盖

## 题目 [区间覆盖](https://www.acwing.com/problem/content/909/)

![[image-3e96944d.png]]

## 思路分析

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

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

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

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

![[image-f9aa8b3e.png]]

所以

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

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

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[区间选点|区间选点]]