基础算法的最后一个内容。题目出自区间合并。
算法的基本流程如下：
- 按区间左端点排序
- 扫描过程中维护一个当前的区间，每次判断
对当前区间st为起点下标，ed为终点下标，则分以下三种状况更新
st ed
|—————————————————|
st ed
① |——————————|
st ed
② |———————————|
st ed
③ |————————————| 排序能够保证对于每一个区间，如果其存在下一个区间，则都是以上三种情况之一。
我们可以一直更新，直到新的st在旧的ed的右侧，说明当前的区间已经合并完成
代码如下
void merge(vector<PII> &segs)
{
vector<PII> ans;
sort(segs.begin(), segs.end()); // PII排序优先左端点，再右端点
int st = -2e9, ed = -2e9;
for (auto seg: segs)
{
if (ed < seg.first)
{
if (st != -2e9) ans.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != -2e9) ans.push_back({st, ed});
segs = ans;
}基础算法完结撒花*★,°*:.☆(￣▽￣)/$:*.°★* ，接下来是数据结构
再吐槽一下自己这篇文章又写得好水
评论（0）
暂无评论