分析一下题目便可得知:
- 第一种情况就是求合并后的区间中,长度最大的区间
- 第二种情况就是求不能合并的区间中,尾首相隔最远的长度
于是乎,直接套用 区间合并 的模板
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> a;
int n;
int ans1,ans2;
void find_area()
{
vector<PII> res;
sort(a.begin(),a.end()); // 按照左节点排序
int st = -2e9,ed = -2e9;
for(auto x : a)
{
// 第二种情况对应 不能合并的区间
if(ed < x.first)
{
// 在更新节点之前就 算ans2
if(ed != -2e9) ans2 = max(ans2,x.first - ed);
if(st != -2e9) res.push_back({st,ed});
st = x.first; ed = x.second;
}
else
{
ed = max(ed,x.second);
}
}
if(st != -2e9) res.push_back({st,ed});
a = res;
for(auto x : a) // 第一种情况就是求最长的合并区间,全部合并完求一下最大区间长度即可
{
ans1 = max(ans1,x.second - x.first);
}
}
int main()
{
cin >> n;
while(n--)
{
int l,r;
cin >> l >> r;
a.push_back({l,r});
}
find_area();
cout << ans1 << ' ' << ans2 << endl;
return 0;
}