AcWing 803. 区间合并
原题链接
简单
作者:
松鼠爱葡萄
,
2020-08-21 16:19:58
,
所有人可见
,
阅读 1183
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> pii;
vector<pii> segs;
int n;
void merge(vector<pii> &segs) {
vector<pii> res;
sort(segs.begin(), segs.end());
int ed = -1e9;
for (auto seg:segs) {
if (ed < seg.first) {
res.push_back({seg.first, seg.second});
ed = seg.second;
} else {
ed = max(ed, seg.second);
}
}
segs = res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size();
}
输入
5
1 2
2 4
5 6
7 8
7 9
输出
1 2
5 6
7 8
错误的
这个不对,只是size() 正确, segs 具体列出不是正确答案
#### 嗯嗯, 作者保存了第一个每一个新加入的区间, 后面没有更新区间。
#### 我觉得这个答案蛮好的, 不用向y总提供的答案,需要判单边界条件。