定义

步骤

1. 按区间左端点排序
2. 分情况讨论
   2.1 不相交（ed < new_st）：st、ed更新为新区间的st、ed
   2.2 相交但不包含 ，ed更新为两者中更大的那一个
   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.second) // 情况1：两个区间无法合并
        {
            if (st != -2e9) res.push_back({st, ed}); // 区间1放入res数组
            st = seg.first, ed = seg.second; // 维护区间2
        }
        else // 情况2：两个区间可以合并
            ed = max(ed, seg.second); // 合并区间
        // 情况3：区间1包含区间2，此时不需要任何操作，可省略
        // 注：排过序之后不可能出现区间2包含区间1
    }

    // 考虑循环结束时st、ed变量，此时的st、ed不需要继续维护，只要不是空输入，只需要放进res数组即可
    if (st != -2e9) res.push_back({st, ed}); // 防止空输入

    segs = res;
}