对于任何一个区间segs,我们需要将他们合并得到一个新的区间数组。比如[1, 2],[2, 3],[5, 7],[6, 9],就可以合并成[1, 3],[5, 9],合并成了两个区间。
方法其实不难,首先我们存储segs数组。然后我们将segs对x从小到大排序,这样就保证了局部有序,合并区间就不会出现缺少的情况。
接下来就是合并操作,先定义临时的区间端点st和ed。然后遍历区间数组。如果当前数组的值的x大于临时数组中的ed,那么就说明当前区间st和ed是无法继续合并的(已经最大了),所以加入到结果中。否则的话,就要更新最大的ed。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; int n; vector<PII> segs;
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.emplace_back(st, ed); st = seg.first, ed = seg.second; }else ed = max(ed, seg.second); } if(st != -2e9) res.emplace_back(st, ed); segs = std::move(res); }
int main() { int n; cin >> n; while(n--) { int x, y; cin >> x >> y; segs.emplace_back(x, y); } merge(segs); cout << segs.size(); return 0; }
|