解题思路:
1:按区间左端点从小到大排序
2:遍历一遍。遍历的同时维护一个区间。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef pair<int, int> PII; 4 void merge(vector<PII> &segs) { 5 vector<PII> res; 6 sort(segs.begin(), segs.end()); 7 //优先以左端点排序,再以右端点排序 8 int st = -2e9, ed = -2e9; //设置一个边界值 9 for (int i = 0; i < segs.size(); i++) { //扫描所有区间 10 if (ed < segs[i].first) { 11 if (st != -2e9) { 12 res.push_back({st, ed}); //找到了一个区间 13 } 14 st = segs[i].first; 15 ed = segs[i].second; 16 } else { 17 ed = max(ed, segs[i].second); 18 } 19 } 20 if (st != -2e9) { //防止输入里没有任何区间 21 res.push_back({st, ed}); 22 } 23 segs = res; 24 } 25 int main() { 26 vector<PII> segs; 27 int n; 28 cin >> n; 29 for (int i = 0; i < n; i++) { 30 int l, r; 31 cin >> l >> r; 32 segs.push_back({l, r}); 33 } 34 merge(segs); 35 cout << segs.size() << endl; 36 return 0; 37 }
原文链接: https://www.cnblogs.com/fx1998/p/12828310.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/360795
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!