# 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 intervalstruct box{    int s;    int e;};// A Boolean compare function to sort intervals with their end timebool cmp(box a,box b){    return a.e < b.e;}// A Boolean function to find if overlap exists or notbool 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)