【题解】区间分组

题目：区间分组

题意：

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

输出最小组数。

输入格式

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

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

输出格式

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

数据范围

1 ≤ N ≤ 10⁵ ,
−10⁹ ≤ ai ≤ bi ≤ 10⁹

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

思路：

• 首先我们要明确，涉及区间的贪心问题一般都是先排序，后处理。至于是根据左端点排序还是根据右端点，需要我们根据实际情况来判断。可以是直觉，也可以根据现实情况或者试一试样例，反正能过就可以了，贪心问题难就难在证明，这么做肯定对，为什么对？说不出来。
• 第一步：将所有区间按左端点从小到大排序（第一步就很奇怪，也许有同学会觉得这道题和 最大不相交区间数量 很像，根据传递性那么这道题应该也根据右端点排序才对，但事实就是需要根据左端点）。
• 第二步：依次枚举每个区间，判断是否能将其放入现有的某个组中 L[i] > Max_r 。
  • 如果不存在这样的组，说明当前区间与现有所有组有冲突，开辟新的组并放入该区间。
  • 如果存在这样的组，将该区间随意放入任何一个可以放入的组中（为什么可以随便放？首先无论我们放入哪个合法的组中，放入后该组的 Max_r 都会更新为该区间的 R[i] ，其次因为我们是根据左端点排序的，所以一定有 L[i+1]>=L[i]，那么这个区间能放入的组后面的区间也一定能放入），并更新该组的 Max_r。
• 如何实现这样的分组？优先队列。因为我们需要维护每个组的 Max_r ，所以我们只需要存每个组的 Max_r 即可，然后每次与队中的首元素比较，如果可以加入就该区间 L[i] 入队并将首元素出队。否则就直接将 L[i] 入队。队列中每个元素表示一个分组。
• 注意，优先队列默认大根堆，如果想让元素从小到大排序需要在定义时补充priority_queue<int,vector<int>,greater<int>>q;

代码

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N=100010;
#define PII pair<int,int>

int n;
PII p[N];
priority_queue<int,vector<int>,greater<int>>q;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>p[i].first>>p[i].second;

    sort(p+1,p+n+1);
    
    for(int i=1;i<=n;++i)
    {
        if(q.size()==0||p[i].first<=q.top())
            q.push(p[i].second);
        else 
        {
            q.pop();
            q.push(p[i].second);
        }
    }
    
    cout<<q.size();
    return 0;

}