当做完区间合并之后的分析
C++ 代码 (总结一下就是,不要少做事,也不要做多此一举的事)
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 5010;
int n;
PII famer[N], res[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
int l = 0, r = 0;
scanf("%d%d", &l, &r);
famer[i] = {l, r};
}
sort(famer, famer + n);
int st = -1e8, ed = -1e8, j = 0;
for (int i = 0; i < n; i ++ )
if (ed < famer[i].first)
{
if (st != -1e8) res[j] = {st, ed}, j ++ ;
st = famer[i].first, ed = famer[i].second;
}
else ed = max(ed, famer[i].second);
if (st != -1e8) res[j] = {st, ed};
int ans1 = 0, ans2 = 0;
for (int i = 0; i <= j; i ++ )
{
ans1 = max(ans1, res[i].second - res[i].first);
if (i <= j - 1) ans2 = max(ans2, res[i + 1].first - res[i].second);
}
cout << ans1 << ' ' << ans2 << endl;
return 0;
}