AcWing 1343. 挤牛奶
原题链接
简单
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n; const int N=5000;
typedef pair<int,int> pa;
vector<pa> ve;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int begin,end; cin>>begin>>end;
auto s=pa{begin,end};
ve.push_back(s);
}
sort(ve.begin(),ve.end());
int count=0;
for(int i=1;i<n;i++)//从第二个区间遍历
{
if(ve[i-count-1].second>=ve[i-count].first)
{
ve[i-count].first=min(ve[i-1-count].first,ve[i-count].first);//合并
ve[i-count].second=max(ve[i-1-count].second,ve[i-count].second);
ve.erase(ve.begin()+i-count-1);//删去上一个区间
count++;
}
}
int ans1=0; int ans2=0;
for(int i=0;i<ve.size();i++)
{
int res1=ve[i].second-ve[i].first;
ans1=max(ans1,res1);
int res2=ve[i+1].first-ve[i].second;
ans2=max(ans2,res2);
}
cout<<ans1<<" "<<ans2;
return 0;
}