如何建立网站管理系统,网站后台管理增加功能,学校网站建设主体,wordpress大淘客主题区间合并使用贪心算法#xff0c;对于区间问题#xff0c;通常需要对左端点排序、右端点排序或者左端点和右端点双关键字排序。区间合并算法的算法步骤#xff1a;
1. 按照区间左端点排序。
2. 扫描过程中#xff0c;每次维护一个当前的区间。 题目链接#xff1a;
htt…区间合并使用贪心算法对于区间问题通常需要对左端点排序、右端点排序或者左端点和右端点双关键字排序。区间合并算法的算法步骤
1. 按照区间左端点排序。
2. 扫描过程中每次维护一个当前的区间。 题目链接
https://www.acwing.com/problem/content/805/
代码
#include iostream
#include algorithm
#include vectorusing namespace std;typedef pairint, int PII;int n;
vectorPII segs;void merge(vectorPII segs)
{vectorPII 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;
}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() endl;return 0;
}
