区间合并

题意

输入$n$个区间，求一共有几个区间有交集

准备

vector<pair<int, int>> seg; // 存储输入的区间

分析

一共有三种情况

1. 输入的区间被当前维护的区间完全包含
2. 输入的区间与当前维护的区间有交集
3. 输入的区间与当前维护的区间无交集

先将所有输入的区间 $[l, r]$按 $l$ 的大小排序。

令当前维护的区间为 $[st, ed]$ ，然后扫描所有区间 $[l, r]$

if (l > ed) 说明属于情况3， 无交集， 将维护的区间更新为 [l, r]
    // st = seg.first, ed = seg.second;
else 属于情况1或2 {
    if (情况1，即 r < ed) 则维护的区间不变
    if (情况2，即 r > ed) 则维护的区间 [st, ed] 更新为 [st, r]
        // ed = seg.second;
    // 可以把两种情况简写为 ed = max(ed, seg.second);
} 

最后返回答案数组的长度即可。

代码

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

using namespace std;

typedef pair<int, int> PII;
int n;
vector<PII> segs, res;

void merge(vector<PII> &segs) {
    // 首先将区间按l的大小排序
    sort(segs.begin(), segs.end());
    // 边界值，因为此题数据范围在-1e9 到 1e9之间，所以这次取两倍
    int st = -2e9, ed = -2e9;
    for (auto seg : segs) {
        // 当扫描到的区间l大于当前维护的区间的ed时
       if (ed < seg.first) {
           // 这个if的作用是防止输入为空时，将{-1e9，-2e9}也当作答案push到res里
           // 将当前维护的区间push到答案数组中
           if (st != -2e9) res.push_back({st, ed});
           // 更新维护的区间
           st = seg.first, ed = seg.second;
       } else {
           // 当扫描到的区间l不大于当前维护的区间的ed时
           ed = max(ed, seg.second);
       }
    }
    // 将当前维护的区间push到答案数组中
    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();

    return 0;
}