区间分组

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

输出最小组数。

输入格式

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

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

输出格式

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

数据范围

1≤N≤1e5
−1e9≤ai≤bi≤1e9

输入样例:

3
-1 1
2 4
3 5

输出样例:

2

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100100;

int n;
int b[2 * N], idx;

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

    sort(b, b + idx);

    int res = 1, t = 0;
    for(int i = 0; i < idx; i ++)
    {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
typedef pair<int, int>PII;
int a[N];
int n;

priority_queue<int,vector<int>,greater<int>> heap;
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};
    }

    sort(range, range + n);
    heap.push(range[0].r);
    for (int i = 1; i < n; i ++ )
    {
       if(range[i].l<=heap.top()) 
       heap.push(range[i].r);
       else
       {
           heap.pop();
           heap.push(range[i].r);
       }
    }

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

    return 0;
}