01_区间合并 merge_interval

区间取并集合并

情况1: 相交
[      ]
    [      ]

情况2: 包含
[      ]
   [  ]

情况3: 错开
[      ]
         [      ]

（1）用二元vector作区间集合

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;    
int n;
vector<PII> segs, res;

int main() {
    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()); // 按左端点排序

    /*
    左端点st是多少无所谓，
    右端点ed设置小点（比给出的数据范围小就行）: 
        因为每次处理右端点都是取最大值，如果ed初始太大，后面无法处理
    */
    int st = 0, ed = -2e9;
    for (auto it : segs) {
        if (ed < it.first) { // 
            /* 
            res 每次 push 的是处理完毕的区间，第一个区间还没处理过，不要，
            后面的区间如果出现 右端点 < 下一个区间的左端点: 情况3: 错开 => 更新左端点 st 和右端点 ed
            */
            if (ed != -2e9) res.push_back({st, ed});
            st = it.first, ed = it.second;
        } else ed = max(ed, it.second); // 情况1&2: 相交和包含 => 右端点 ed 取最大 
    }
    res.push_back({st, ed}); // 把最后一个处理完成的区间 push 到 res

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

    return 0;
}

（2）用二元数组作区间集合

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
int n, res;
PII a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

    sort(a, a + n); // 按左端点排序

    int ed = a[0].second;
    for (int i = 1; i < n; i++) {
        if (ed >= a[i].first) ed = max(ed, a[i].second); // 情况1&2: 相交和包含 => 右端点 ed 取最大
        else res++, ed = a[i].second; // 情况3: 错开 => 更新右端点 ed
    }

    cout << res + 1 << endl; // 从第二个区间开始增加计数的，所以+1

    return 0;
}