803. 区间合并（算法基础课第一讲：基础算法）

区间的并

按左端点排序，维护不相交的区间
题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9; // 当前维护的区间
    for(auto &seg : segs)
    {
        if(ed < seg.first)
        {
            if(st != -2e9) res.push_back({st, ed}); // 不相交，把前一段区间 拎出来
            st = seg.first, ed = seg.second; // 更新为 新的区间
        }
        else ed = max(ed, seg.second);
    }

    if(st != -2e9) res.push_back({st, ed}); // 把最后的区间加入

    segs = res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

905. 区间选点（算法基础课第六讲：贪心）

区间的交

按右端点排序， 维护不相交的区间
题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W) const // 重载<, 按右端点排序
    {
        return r < W.r;
    }
}range[N];

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

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
    {
        if(range[i].l > ed)
        {
            res ++ ;
            ed = range[i].r; // 每次选择区间 右端点
        }
    }

    printf("%d\n", res);

    return 0;
}