区间合并

给定多个区间，将有重叠的合并到一起

1. 按区间的左端点排序；
2. 从左到右扫描，维护一个当前区间（随着遍历，若相交则区间变长）
3. 每次遍历的区间和当前区间有三种情况分类讨论：
   • 右端点小于当前区间右端点，当前区间不变；
   • 右端点大于当前区间右端点，当前区间变长；
   • 左端点大于当前区间右端点，将该区间置为当前区间；

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

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

    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;
}

题目

合并区间