题目描述

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入样例

5
1 2
2 4
5 6
7 8
7 9

输出样例

3

区间合并(贪心)

• 用vector<PII>存区间, 处理完输入后, 对pair排序(先左端点, 然后右端点的双关键字排序), 对区间进行合并, 最后输出数组的长度, 即区间数.
• 在进行merge操作时, 传入的数组需要加引用.

• 初始化区间左端点和区间右端点为负无穷, 然后遍历数组, 前后区间进行比较时, 有三种情况

  上一区间的右端点在这个区间的左端点的左边, 也就是两个区间没有交集
  上一区间包含了这个区间
  上一区间和这个区间有交集, 但不是包含关系

• 第一种情况直接将旧数组的左右端点存进res数组, 同时要特判一下左端点不是负无穷(不能把初始的区间放进res)

• 第二种情况和第三种情况可以写成一种, 就是更新一下右端点.
• 最后将最后一个没有比较的区间放进res里, 这里也要判断一下, 防止一开始没有读进任何区间, 从而把初始的负无穷放到res数组里

C++ 代码

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

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs) {
    vector<PII> 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});

    segs = res;
}

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

    vector<PII> segs;

    while (n -- ) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

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

    merge(segs);

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

    return 0;
}