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 ; Function to check if any two intervals overlap ; Find the overall maximum element ; Initialize an array of size max_ele ; starting point of the interval ; end point of the interval ; Calculating the prefix Sum ; 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 isIntersect ( Interval arr [ ] , int n ) { int max_ele = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( max_ele < arr [ i ] . end ) max_ele = arr [ i ] . end ; } int aux [ max_ele + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { int x = arr [ i ] . start ; int y = arr [ i ] . end ; aux [ x ] ++ , aux [ y + 1 ] -- ; } for ( int i = 1 ; i <= max_ele ; i ++ ) { aux [ i ] += aux [ i - 1 ] ; if ( aux [ i ] > 1 ) 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 ; }