区间合并问题
不过换了种输出方法,求区间最长的值,以及合并后的区间中,两个相邻区间的距离的最大值
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
int N;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(),segs.end());
int st = -2e6 , ed = -2e6;
for(auto seg:segs)
{
if(ed < seg.first)
{
if(ed != -2e6) res.push_back({st,ed});
st = seg.first;
ed = seg.second;
}
else ed = max(ed,seg.second);
}
if(st != -2e6) res.push_back({st,ed});
segs = res;
}
int main()
{
cin>>N;
while(N--)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
int length1 = 0;
for(int i=0;i<segs.size();i++)
{
length1 = max(length1,segs[i].second - segs[i].first);
}
int length2 = 0;
for(int i=0;i<segs.size()-1;i++)
{
length2 = max(length2,segs[i+1].first - segs[i].second);
}
cout<<length1<<" "<<length2<<endl;
return 0;
}