Check if given intervals can be made non | Function to check if two intervals overlap with each other ; Condition to check if the intervals overlap ; Function to check if there is a existing overlapping intervals ; Path compression ; Union of two intervals Returns True if there is a overlapping with the same another interval ; Both have same another overlapping interval ; Function to check if the intervals can be added by X to form non - overlapping intervals ; If the intervals overlaps we will union them ; There is no cycle ; Driver Code
function checkOverlapping ( a , b ) { if ( a [ 0 ] < b [ 0 ] ) { var temp = a [ 0 ] ; a [ 0 ] = b [ 0 ] ; b [ 0 ] = temp ; temp = a [ 1 ] ; a [ 1 ] = b [ 1 ] ; b [ 1 ] = temp ; } if ( b [ 0 ] <= a [ 0 ] && a [ 0 ] <= b [ 1 ] ) return true ; return false ; } function find ( a , i ) { if ( a [ i ] == i ) { return i ; } a [ i ] = find ( a , a [ i ] ) ; return a [ i ] ; } function union ( a , x , y ) { var xs = find ( a , x ) ; var ys = find ( a , y ) ; if ( xs == ys ) { return true ; } a [ ys ] = xs ; return false ; } function checkNonOverlapping ( arr , n ) { var dsu = [ ] ; for ( var i = 0 ; i < n + 1 ; i ++ ) { dsu . push ( i ) ; } for ( var i = 0 ; i < n ; i ++ ) { for ( var j = i + 1 ; j < n ; j ++ ) { if ( checkOverlapping ( arr [ i ] , arr [ j ] ) ) { if ( union ( dsu , i , j ) ) { return false ; } } } } return true ; } var arr = Array ( ) ; arr . push ( [ 1 , 4 ] ) ; arr . push ( [ 2 , 2 ] ) ; arr . push ( [ 2 , 3 ] ) ; var n = arr . length ; if ( checkNonOverlapping ( arr , n ) ) { document . write ( " " ) ; } else { document . write ( " " ) ; }