题目描述

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

样例

3
-1 1
2 4
3 5

2

算法1

(贪心，小根堆，队列)

1. 将左右端点放入队列q中
2. 对所有区间进行 左端点排序
3. 建立一个小根堆minheap
4. 维护所有区间的右端点
5. 如果新遍历到的区间的 左端点比 右端点小，则新开辟一个新的区间；否则将区间加入，更新 堆顶元素，也就是minheap.pop()

时间复杂度

$O(n)$

C++ 代码

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

using namespace std;

typedef pair<int,int> PII;

const int N = 100010;

PII q[N];

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

    sort(q, q + n);
    priority_queue<int, vector<int>, greater<int>> minheap;

    int res = 1;
    minheap.push(q[0].second);

    for(int i = 1; i < n; i ++)
    {
        if(q[i].first <= minheap.top())
        {
            minheap.push(q[i].second);
            res ++;
        }
        else
        {
            minheap.pop();
            minheap.push(q[i].second);
        }
    }

    cout << res << endl;
    return 0;
}

算法2

(贪心，小根堆，结构体)

时间复杂度

$O(n^2)$

C++ 代码

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

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    // **3
    sort(range, range + n);

    priority_queue<int, vector<int>, greater<int> > heap;
    for(int i = 0; i < n; i ++)
    {
        auto ra = range[i];
        if(heap.empty() || heap.top() >= ra.l) heap.push(ra.r);  // **2
        else
        {
            heap.pop();       // **1
            heap.push(ra.r);
        }
    }

    printf("%d\n", heap.size());

    return 0;
}