生活随笔
收集整理的這篇文章主要介紹了
区间合并板子
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
按照左端點進行排序，然后根據右端點的取值來看區間是否相交。
st和ed表示當前沒有與之相交的區間的左端點和右端點，初始化設置為負無窮。對于正在處理的區間，如果ed小于當前的左端點，說明沒有交集，可以把該當前的{st,ed}放入結果vector中。如果ed大于等于當前區間的左端點，說明有交集，此時ed取區間的右端點和ed之間的最大值。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e5+10;
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(ed!=-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});//放到vector里面}merge(segs);//合并cout<<segs.size()<<endl;/* for(auto seg:segs){cout<<seg.first<<" "<<seg.second<<endl;}*/return 0;}
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的区间合并板子的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
