区间选点

⬅ 返回

1、题目

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

2、解法

3、代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
const int MAX_INT = 0x3f3f3f3f;
struct Node{
    int l,r;
};
bool cmp(Node n1,Node n2)
{
    return n1.r<n2.r;
}
Node node[N];
 
 
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>node[i].l>>node[i].r;
    }
    
    sort(node+1,node+1+n,cmp);
    
    int ans = 0,rd=-MAX_INT;
    for(int i=1;i<=n;i++)
    {
        if(node[i].l>rd)//只有当前区间的左端点大于维护的右边界时 更新边界
        {
            ans++;
            rd=node[i].r;
        }
    }
    cout<<ans<<endl;
}