---
title: "区间选点"
created: 2025-11-28
tags:
  - 算法
---

# 区间选点

## 题目 [区间选点](https://acwing.com/problem/content/907/)

![[image-c6913d01.png]]

## 思路分析

数轴上有一些区间，在数轴上选取几个点，要求每个区间上最少有一个点

其实是一个区间交集的问题 区间问题根据前面区间合并的经验 肯定是要先排序的 然后对于交集问题 贪心的想法是 靠前的区间要与后面的区间有交集
肯定是在右半部分 若右半都与后面一个区间没交集 左边就更不要说了 再贪一点其实就是只要看每个区间的右端点了呗

1、将区间按右端点排序

2、遍历区间，end值初始化为无穷小

如果本次区间不能覆盖掉上次区间的右端点，`ed < range[i].l`，说明需要选择一个新的点，`res ++ ; ed = range[i].r;`

如果本次区间可以覆盖掉上次区间的右端点，则进行下一轮循环

3、输出所选点的个数

![[image-484d3b41.png]]

**证明：**

假设最优解为 ans 个点，贪心算法求出的为 cnt 个点。 只需要证明 ans == cnt 即可。

因为 ans 是最优解，所以 ans <= cnt。

贪心算法求出的结果为 cnt,每次让选取点数+1的区间一定不相交。共计cnt个这样的区间。，为了覆盖这cnt个区间, 至少需要cnt个点。所以ans
>= cnt。

![[image-cb5e4aaf.png]]

综上： cnt == ans

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n;

struct Range{

    int l,r;

    bool operator< (const Range &w)const{

        return r<w.r;

    }

}ranges[N];

int main()

{

    cin>>n;

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

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

    sort(ranges,ranges+n);

    int res=0;

    int ed=-2e9;

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

        if(ranges[i].l>ed){

            res++;

            ed=ranges[i].r;

        }

    }

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[区间覆盖|区间覆盖]] 🏠 [[00-刷题理模型]] ➡️ [[最大不相交区间数量|最大不相交区间数量]]