➤ Problem Link : 1029C. Maximal Intersection
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int n;
cin>>n;
pair<ll,ll> arr[n+1];
for(int i=1;i<=n;i++)
cin>>arr[i].first>>arr[i].second;
pair<ll,ll> cuml[n+2];
pair<ll,ll> cumr[n+2];
cuml[0]=make_pair(LONG_MIN,LONG_MAX);
cumr[n+1]=make_pair(LONG_MIN,LONG_MAX);
ll left,right;
for(ll i=1;i<=n;i++)
{
if(cuml[i-1]==make_pair((ll)-1,(ll)-1))
cuml[i]=cuml[i-1];
else
{
if(arr[i].first > cuml[i-1].second || arr[i].second < cuml[i-1].first)
cuml[i]=make_pair(-1,-1);
else
{
left=max(cuml[i-1].first,arr[i].first);
right=min(cuml[i-1].second,arr[i].second);
cuml[i]=make_pair(left,right);
}
}
}
for(ll i=n;i>=1;i--)
{
if(cumr[i+1]==make_pair((ll)-1,(ll)-1))
cumr[i]=cumr[i+1];
else
{
if(arr[i].first > cumr[i+1].second || arr[i].second < cumr[i+1].first)
cumr[i]=make_pair(-1,-1);
else
{
left=max(cumr[i+1].first,arr[i].first);
right=min(cumr[i+1].second,arr[i].second);
cumr[i]=make_pair(left,right);
}
}
}
ll ans=0;
for(ll i=1;i<=n;i++)
{
pair<ll,ll> a = cuml[i-1];
pair<ll,ll> b = cumr[i+1];
if(a==make_pair((ll)-1,(ll)-1) || b==make_pair((ll)-1,(ll)-1))
continue;
if(a.first > b.second || a.second < b.first)
continue;
left = max(a.first,b.first);
right= min(a.second,b.second);
ans=max(ans,right-left);
// cout<<i<<" "<<left<<" "<<right<<" "<<ans<<endl;
}
cout<<ans;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.