区间合并

可能出现的情况

例题

算法

• 定义一对st、ed记录当前区间的下标
• 需要对输入的区间对，按照first进行排序
• 遍历存储的区间对segs，比较ed 与 seg.first，根据三种不同的情况更新st 和 ed

C++实现

#include
#include
#include
using namespace std;

typedef pair PII;

vector segs;

int n;

void merge_segs (vector &segs) {
    vector res;
    
    sort (segs.begin(), segs.end());    // pair按照first排序
    
    int st = -2e9, ed = -2e9;
    for (PII 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;
    
    while (n --) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    merge_segs(segs);
    
    cout << segs.size();
    
    return 0;
}