题目描述

给定N个闭区间[ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。 输出最小组数。

输入格式
第一行包含整数N，表示区间数。

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

输出格式
输出一个整数，表示最小组数。

数据范围
1 ≤ N ≤ 10^5,
−10^9 ≤ ai ≤ bi ≤ 10^9

样例

输入样例：
3
-1 1
2 4
3 5
输出样例：
2

算法1

用小根堆优化 O(nlogn)

【解析】

小根堆 priority_queue<int, vector<int>, greater<int>> heap; 

1、首先将所有区间按左端点从小到大排序;
2、从前往后依次枚举区间，
判断已存入的区间最大右端点值 是否大于 当前区间左端点值？
是, 需要开一个新组，然后再将其放进组中；
否则放上一个区间组里，并更新到当前区间的右端点值；

3、一定存在一种合理方案，使得按照方案得到的组数，为方案的最小值。

C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int N=1e5+10;
int n;

struct Range
{
    int l, r;
    bool operator < (const Range &w) const 
    {
        return l < w.l;
    }
}range[N];

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)  cin>>range[i].l >>range[i].r;
    sort(range,range+n);

    priority_queue<int, vector<int>, greater<int>> heap;  //用heap.size() 表示组数
    for(int i=0; i<n; i++)
    {
        if(heap.empty() || heap.top()>= range[i].l )  //判断已存入的区间最大右端点值 是否大于 当前区间左端点值?
        {                                               //是, 需要开一个新组，
            heap.push(range[i].r);                   
        }
        else                                            //否则放入上一个区间组里，更新区间最右端点值；
        {
            heap.pop();
            heap.push(range[i].r);
        }
    }
    cout<<heap.size();

    return 0;
}