题目描述
给n个挤奶工的工作时间,求最长的有人工作的连续区间,和最长的连续没人工作的区间。
即给n个区间,求最长的连续区间和最长的间断区间。
样例
输入样例
3
300 1000
700 1200
1500 2100
输出样例
900 300
解题代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
vector<PII> segs;
int n;
int a,b; // a存最长的工作区间,b存最长的间断区间
int main()
{
scanf("%d",&n);
for(int i = 0 ; i < n ; i++)
{
PII a;
scanf("%d%d",&a.x,&a.y);
segs.push_back(a);
}
sort(segs.begin(),segs.end()); // 按左端点排序
int st = -2e9,ed = -2e9;
for(auto seg:segs)
{
if(ed < seg.x)
{
if(st != -2e9 && ed != -2e9) a = max(a,ed - st),b = max(b,seg.x - ed); // 有新的区间,更新最长的区间结果
st = seg.x,ed = seg.y; // 更新新的区间
}
else ed = max(ed,seg.y); // 更新当前区间
}
if(st != -2e9 && ed != -2e9) a = max(a,ed - st); // 用最后一个连续区间更新结果
cout << a << ' ' << b;
return 0;
}