How to find Non-Overlapping Intervals using C++



If you are given 'n' number of intervals, how do you find the non-overlapping ones.

Consider a example:

n = 6

intervals = [ { 1,3 }, { 4,6 } ,{ 7,9 } ,{ 2,4 } ,{ 6,7 } ,{ 8,10 }]

{ a,b } ->  a=start time; b= end time;

Output: [{ 4,6 }, { 6 ,7 }]

The approach that I have used in this problem is simple:

1. Sort the input according to their end time.

2. Take a loop from 0 to n-1. This part has 3 important steps ( Let's say loop variable is 'i' ):

2.1 If i==0, check if it overlaps with next element

2.2 if i > 0 and i < n-1, check if it overlaps from left and right side.

2.3 if i==n-1 check if it overlaps with previous element

To check if overlap is there between interval x and y, it is simple just check if y.start >= x.end; if not true then there is a overlap.

The complexity of this algorithm remains O(n*log(n)).

Since sorting takes O(n*log(n)) and loop takes O(n).

#include<bits/stdc++.h>
using namespace std;
// Defining interval
struct box{
int s;
int e;
};
// A Boolean compare function to sort intervals with their end time
bool cmp(box a,box b){
return a.e < b.e;
}
// A Boolean function to find if overlap exists or not
bool doesOverlap(box a,box b){
if(b.s >= a.e) // no overlap
return true;
return false; // overlap
}
vector<box> findThemAll(box v[],int n){
// Declaring a vector that will hold our non-overlapping intervals
vector<box>vec;
// Sorting the intervals with end time
sort(v,v+n,cmp);
// Checking our logic for every interval
for(int i=0;i<n;i++){
// A Boolean variable to tell if present element overlaps or not
bool pick_element = false;
if(i==0){
if(n==1) // if only one interval exists then return that
pick_element = true;
else if(doesOverlap(v[i],v[i+1]))
pick_element = true;
}
else if(i>0 && i<n-1){
if(doesOverlap(v[i],v[i+1]) && doesOverlap(v[i-1],v[i]))
pick_element = true;
}
else{
if(doesOverlap(v[i-1],v[i]))
pick_element = true;
}
// Non-Overlapping interval is stored
if(pick_element)
vec.push_back(v[i]);
}
return vec;
}
int main(){
cout << "How many number of intervals?n";
int n;
cin >> n;
box v[n];
cout << "Enter a b : a-> start time, b-> end time n";
for(int i=0;i<n;i++)
cin >> v[i].s >> v[i].e;
vector<box> vec = findThemAll(v,n);
cout << "The non-overlapping intervals are:n";
// Print if there are elements in vector
if(!vec.empty()){
for(auto x:vec){
cout << "[" << x.s << ", " << x.e << "]n";
}
}
else
cout << "All intervals are overlappingn";
return 0;
}

If you find any mistakes or have any suggestions, please let me know.

Peace :)


Suhaib Bin Younis | @suhaibbinyounis

Post a Comment

Post a Comment (0)

Previous Post Next Post