Check if any two intervals intersects among a given set of intervals | A C ++ program to check if any two intervals overlap ; An interval has start time and end time ; Compares two intervals according to their staring time . This is needed for sorting the intervals using library goo . gl / iGspV function std :: sort ( ) . See http : ; Function to check if any two intervals overlap ; Sort intervals in increasing order of start time ; In the sorted array , if start time of an interval is less than end of previous interval , then there is an overlap ; If we reach here , then no overlap ; Driver program
#include <algorithm> NEW_LINE #include <iostream> NEW_LINE using namespace std ; struct Interval { int start ; int end ; } ; bool compareInterval ( Interval i1 , Interval i2 ) { return ( i1 . start < i2 . start ) ? true : false ; } bool isIntersect ( Interval arr [ ] , int n ) { sort ( arr , arr + n , compareInterval ) ; for ( int i = 1 ; i < n ; i ++ ) if ( arr [ i - 1 ] . end > arr [ i ] . start ) return true ; return false ; } int main ( ) { Interval arr1 [ ] = { { 1 , 3 } , { 7 , 9 } , { 4 , 6 } , { 10 , 13 } } ; int n1 = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) ; isIntersect ( arr1 , n1 ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; Interval arr2 [ ] = { { 6 , 8 } , { 1 , 3 } , { 2 , 4 } , { 4 , 7 } } ; int n2 = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ] ) ; isIntersect ( arr2 , n2 ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; return 0 ; }