贪心

区间选择问题

区间问题

区间合并

Acwing 3302. 表达式求值

思路： 把所有区间按左端点排序，再依次从左往右遍历：

1. 如果遍历到的区间左端点在当前区间右端点右边(即两区间未重合)，计数区间，并把当前区间更新
2. 如果遍历到的区间左端点在当前区间右端点左边或相等(即两区间重合)，不需要计数，把两区间合并(当前区间的右端点取最大的)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<pair<int,int>> VII;

VII segs;

void merge(VII &segs){
    VII res;

    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});
    // 把最后一个区间压入，如果根本就没区间输入，需要排除初始值[-2e9, -2e9]

    segs = res;
}

int main(){
    int n;
    cin >> n;

    for (int i =0 ; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    sort(segs.begin(), segs.end()); // pair 默认先排序 first 再排序 second

    merge(segs);

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

    return 0;
}

分配问题

贪心背包

最小生成树

Prim

详细请看图章节最小生成树 Prim

Kruscal

详细请看图章节最小生成树 Kruscal