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