贪心——区间问题（二）

区间分组

image.png

目标是给给定的所有区间分组，然后每一个组中的所有区间都没有交集，然后尽可能的组数要少一些。

核心——找出一个组，尽可能地把所有区间放进去，重点是这些区间不能有交集。

解决方案——将所有区间按照左端点排序，然后维护每一组中，该组中所有区间中，右端点的最大值。当来了一个新的区间的时候，如果当前这个新区间的右端点比所有组的右端点都小（也就是在其左边），则必须新开一个新的组(组数res ++)。否则可以将这个新区间加入到右端点最小（最靠左）的那一组中，然后更新该组的右端点。

C++ 代码

一开始将第1个区间加入，当做第1组，如果后面的区间进来，符合条件就res ++，不然就加入原先的第一组，记着要pop掉原先堆中的堆顶。因为可能新进来这个区间的右端点比原先的要小，所以不pop掉会WA。
这个最小堆维护的是一个存储每一个组中所有区间的右端点的最小值。如果新来的区间跟最小值都有交集，那么确实得新开一个组了。

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

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

int n;
int l, r;
PII q[N];
priority_queue<int, vector<int>, greater<int>> heap;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &l, &r);
        q[i] = {l, r};
    }
    sort(q, q + n);
    
    int res = 1;
    heap.push(q[0].second);
    
    for(int i = 1; i < n; i ++)
        if(q[i].first <= heap.top())
        {
            res ++;
            heap.push(q[i].second);
        }
        else
        {
            heap.pop();
            heap.push(q[i].second);
        }
    
    cout << res << endl;
    
    return 0;
}