AcWing 803. 区间合并
原题链接
简单
作者:
我要出去乱说
,
2021-02-19 15:40:11
,
所有人可见
,
阅读 199
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int n;
vector<PII> seg, res;
void merge()
{
int st = -2e9, ed = -2e9;
for (auto item : seg)
{
if (ed < item.first) //该段末尾小于下段开头
{
if (st != -2e9) res.push_back({st, ed}); //储存这一段
st = item.first, ed = item.second; //更新下一段
}
else
{
ed = max(ed, item.second); //两段合并为一段,只要挪动ed即可
}
}
if (st != -2e9) res.push_back({st, ed}); //判空并处理最后一段
} //题目给出n不为0,所以不用这个if判空也能通过
int main()
{
cin >> n;
while (n -- )
{
int l, r;
cin >> l >> r;
seg.push_back({l, r});
}
sort(seg.begin(), seg.end());
merge();
cout << res.size() << endl;
return 0;
}