// 将所有存在交集的区间合并
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; // 更新原来的区间集合
}
-
首先对所有区间按左端点从小到大进行排序,这样可以使得相邻的区间更容易合并。
-
然后初始化两个变量st和ed,分别表示当前合并区间的起点和终点。初始值为-2e9,表示一个极小值。
-
对于每个区间,如果它的左端点大于当前合并区间的右端点ed,说明当前区间和前面的区间没有交集,将当前合并区间加入结果集res中,并将st和ed更新为当前区间的左右端点。
-
如果当前区间和前面的区间有交集,将当前区间的右端点更新为ed和当前区间右端点的最大值,这样可以使得合并后的区间更长。
-
最后,如果存在未加入结果集的合并区间,将其加入结果集中。
-
最后将原始区间集合segs更新为合并后的结果集res。
时间复杂度为$O(nlogn)$,其中$n$为区间的个数,主要由排序操作引起。