Check if any two intervals intersects among a given set of intervals | A Java 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
class GFG { static class Interval { int start ; int end ; public Interval ( int start , int end ) { super ( ) ; this . start = start ; this . end = end ; } } ; static boolean 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 = new int [ max_ele + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { int x = arr [ i ] . start ; int y = arr [ i ] . end ; aux [ x ] ++ ; aux [ y ] -- ; } for ( int i = 1 ; i <= max_ele ; i ++ ) { aux [ i ] += aux [ i - 1 ] ; if ( aux [ i ] > 1 ) return true ; } return false ; } public static void main ( String [ ] args ) { Interval arr1 [ ] = { new Interval ( 1 , 3 ) , new Interval ( 7 , 9 ) , new Interval ( 4 , 6 ) , new Interval ( 10 , 13 ) } ; int n1 = arr1 . length ; if ( isIntersect ( arr1 , n1 ) ) System . out . print ( "YesNEW_LINE"); else System . out . print ( "NoNEW_LINE"); Interval arr2 [ ] = { new Interval ( 6 , 8 ) , new Interval ( 1 , 3 ) , new Interval ( 2 , 4 ) , new Interval ( 4 , 7 ) } ; int n2 = arr2 . length ; if ( isIntersect ( arr2 , n2 ) ) System . out . print ( "YesNEW_LINE"); else System . out . print ( "NoNEW_LINE"); } }