步骤

（1）按照各个区间的左端点进行排序
（2）对区间进行合并

时间复杂度

时间复杂度的瓶颈在排序上，所以为O(NlogN)。N为原始区间的个数。

模板

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st = -1, en = -1;
    for(auto & v : segs)
    {
        if(en < v.first)
        {
            if(st != -1) res.push_back({st,en});
            st = v.first, en = v.second;
        }
        else en = max(v.second,en);
    }
    if(st != -1) res.push_back({st,en});
    segs = res;
}

传入的segs为原始的区间的集合，最终经过merge函数后segs为区间合并之后的区间集合。

板子题

传送门