最大不相交区间

简介: 最大不相交区间

给定 N 个闭区间 [ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。


输出可选取区间的最大数量。


输入格式

第一行包含整数 N,表示区间数。


接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。


输出格式

输出一个整数,表示可选取区间的最大数量。


数据范围

1≤N≤10^5

−10^9≤ai≤bi≤10^9

输入样例:
1. 3
2. -1 1
3. 2 4
4. 3 5
输出样例:
2

思路:这个题代码和上一个题完全一致(区间问题之区间选点-CSDN博客)

观察下图1,2,3中存在一个点覆盖了三个区间,其实可以转换成1,2,3中选区间只能选出一个区间使得1,2,3不冲突。就是把1,2,3看成一个整体,那么在这个整体中只能选出一个区间,多一个都会有交集。


完整代码:

#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int N=1e5+10;
struct range{
    int l,r;
    bool operator< (const range &w)const{
        return r<w.r;
    }
};
range range[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>range[i].l>>range[i].r;
    sort(range,range+n);
    int count=0,temp=-2e9;
    for(int i=0;i<n;i++)
    {
        int temp=range[i].r;
        count++;
        while(temp>=range[i+1].l&&temp<=range[i+1].r)i++;
    }
    cout<<count;
}
相关文章
|
6月前
leetcode-435:无重叠区间
leetcode-435:无重叠区间
32 0
|
6月前
|
机器学习/深度学习 算法 测试技术
【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II
【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II
【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II
|
6月前
|
人工智能 BI
区间问题之区间选点
区间问题之区间选点
|
6月前
|
C++
汇总区间(C++)
汇总区间(C++)
53 0
|
6月前
leetcode-352:将数据流变为多个不相交区间
leetcode-352:将数据流变为多个不相交区间
42 0
|
11月前
|
算法 测试技术 C#
C++二分查找算法的应用:将数据流变为多个不相交区间
C++二分查找算法的应用:将数据流变为多个不相交区间
判断两个链表是否相交,相交的话返回相交的节点
1.判断是否相交 找到两个链表的最后一个节点,看是否相同,相同的话就相交,反之. 2.找两个链表长度的差值 为什么要找两个链表的差值呢? 为了判断哪个长,以便让长的链表先走差值,方便找相交处 3.找相交处 长的走后,再便利长的和短的一起走,以找到相交节点
39 0
|
人工智能 算法 BI
贪心算法——区间选点与最大不相交区间数
贪心算法——区间选点与最大不相交区间数
68 0
判断线段是否相交
判断线段是否相交
87 0