Sweep Line Technique : The Secret Weapon for Range & Geometry Problems , Part-2
Optimize Event Processing and Interval Queries Like a Pro
I break down complex programming and DSA topics into simple, beginner-friendly explanations. Currently learning, building, and sharing my journey in tech.
Sweep Line Ideas :
Question :-
Given N Intervals Of The Form -> L,R
N<=10^5
L,R <= 10^9
1 - Find Union Of All :
The union of two sets contains all elements from both sets, with common elements included only once
Example :
Intervals :
[1,5]
[3,7]
Number line: 1----5
Number line: 3----7
Union = [1,7]
Even though they overlap, union merges them.
If intervals are :
[1,5]
[7,9]
These do Not overlap and there is a gap between 5 and 7.
So the union is simply both intervals as they are : Union = [1,5] U [7,9]
No merging happens because there is no overlap or touching.
(If it were [1,5] and [5,9], then they touch, so union would be [1,9].)
Let’s find the union of these intervals :
[6,8]
[3,7]
[4,5]
[2,5]
Final Answer = [2,8] → Union
2 - Find Intersection Of All(Portion that is common to all intervals.)
Think :
- Where all intervals overlap together.
Example :
Intervals :
[1,5]
[3,7]
Common region = [3,5]
This is where both intervals exist at the same time.
Answer For Intersection :-
Max(Li) , Min(Ri) → Of All The Intervals…
If __ > __ -> No Intersection
An intersection exists only if the left of one interval is less than or equal to the right of another interval.
So, to check whether an intersection exists among all given intervals, it is sufficient to take the maximum of all left (max Li) and the minimum of all right (min Ri) and compare them
Why max L and min R ?
Think Like a Meeting Time
Imagine 3 friends tell you when they are free :
Friend A: 1 to 5
Friend B: 2 to 6
Friend C: 4 to 8
You want one time when All are free.
Step 1 — Latest Start (max Li) :
Starts are: 1, 2, 4
Latest start = 4
Before 4, friend C is not free.
So meeting cannot be before 4.
Step 2 — Earliest End (min Ri) :
Ends are: 5, 6, 8
Earliest end = 5
After 5, friend A is busy.
So meeting cannot be after 5.
So You must meet after 4 and before 5.
____________________________ _______________
___________________________ ________________________________________
| | | | | | | |
+1 +1 -1 -1 +1 +1 -1 -1
N=2
[1,5]
[3,7]
Common Region = [3,5] -> Intersection
_________
1 5
_________
3 7
_________________
1 2 3 4 5 6 7 8 9 -> Axis
N=4
[6,8]
[3,7]
[4,5]
[2,5]
_______
2 5
_________
3 7
___
4 5
_____
6 8
_________________
1 2 3 4 5 6 7 8 9 -> Axis
No Common Region
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<pair<int,int>> events;
for(int i=0; i<n; i++)
{
int l,r;
cin>>l>>r;
events.push_back({l,+1});
events.push_back({r,-1});
}
sort(events.begin(),events.end());
int cnt=0;
int Union=0; // Storing The Total Length Of Union
int Intersection=0; // Storing The Total Length Of Intersection
for(int i=0;i<events.size()-1;i++)
{
cnt+=events[i].second;
if(cnt>0)
{
Union += events[i+1].first - events[i].first;
}
if(cnt==n)
{
Intersection += events[i+1].first - events[i].first;
/*
This condition becomes true only if the current region is covered by all n intervals -> the intersection region.
If the intersection does not exist, cnt == n is never true, so intersection length stays 0.
*/
}
}
cout<<Union<<" "<<Intersection<<endl;
return 0;
}
We count union only when cnt > 0 because
When cnt == 0, no interval covers that region, so it must not be included.
Use the below example to understand why we count union only when cnt > 0 :
Question :
N Segments(<=10^5)
Each Segment Contains L,R,X (Inclusive)
Q Queries(<=10^5)
Each Query Contains ? Y (Find Max X For Any Interval That Contains Y In It)
___ X = 7
5 6
______________ X = 6
4 10
___________ X = 5
2 7
________ X = 2
12 14
______________________________________
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 -> Axis
.
5,6,7 (7 Is The Answer)
.
6 (6 Is The Answer)
If This Is The Interval __________________________________________
Insert Operation Remove Operation
If This Is The Query .Query Operation
Intervals Are Inclusive Sooooo.............
If Insert,Remove,Query All Are Happening At The Same Point
. Remove
. Query
. Insert
Then First Insert Should Happen Then Query Then Remove
I 0th Priority
Q 1st Priority
R 2nd Priority
If Intervals Are Exclusive.............
If Insert,Remove,Query ALL Are Happening At The Same Point
. Remove
. Query
. Insert
Then First Remove Should Happen Then Query Then Insert
R 0th Priority
Q 1st Priority
I 2nd Priority
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<pair<int,pair<int,int>>> events;
for(int i=0;i<n;i++)
{
int l,r,x;
cin>>l>>r>>x;
events.push_back({l,{0,x}});
events.push_back({r,{2,x}});
}
int q;
cin>>q;
for(int i=0;i<q;i++)
{
int y;
cin>>y;
events.push_back({y,{1,i}});
}
sort(events.begin(),events.end());
multiset<int> mt;
int ans[q];
for(int i=0;i<events.size();i++)
{
if(events[i].second.first==0) //Insert
{
mt.insert(events[i].second.second);
}
else if(events[i].second.first==2) //Remove
{
mt.erase(mt.find(events[i].second.second));
}
else //Query
{
if(mt.empty())
{
ans[events[i].second.second]=-1;
}
else
{
ans[events[i].second.second]=*mt.rbegin();
}
}
}
for(int i=0;i<q;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
