AcWing 1343. 挤牛奶
原题链接
简单
作者:
OI_IO
,
2024-03-14 13:13:23
,
所有人可见
,
阅读 15
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
typedef pair<int, int> PII;
PII segs[N];
int n;
int main()
{
cin >> n;
for (int i = 0; i < n; i ++) scanf("%d %d", &segs[i].first, &segs[i].second);
sort(segs, segs+n); //进行区间排序,以first端点进行排序
int l = segs[0].first, r = segs[0].second; //先进行初始化,区间为第一个区间
int res1 = r - l, res2 = 0; //分别表示最长连续挤奶时间(先设置为第一段)和最长连续无人挤奶时间
for (int i = 1; i < n; i ++) //从第二个区间进行枚举
{
if (segs[i].first > r) //如果区间2的左端点大于区间1的右端点,说明没有交集,可以开始计算
{
res1 = max(res1, segs[i].second - segs[i].first); //区间2和区间1挤奶时间进行比较
res2 = max(res2, segs[i].first - r); //区间2的起始时间减去区间1的结束时间为无人挤奶时间
l = segs[i].first, r = segs[i].second; //进行区间更新
}
else //如果区间2的左端点小于等于区间1的右端点,则说明有交集,进行区间合并
{
r = max(r, segs[i].second);
res1 = max(res1, r - l); //区间拓展会影响最长连续挤奶时间,再次进行比较
}
}
cout << res1 << ' ' << res2 << endl;
return 0;
}