Check if given intervals can be made non | Java implementation to check if the intervals can be non - overlapping by by adding or subtracting X to each interval ; 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
import java . io . * ; import java . util . * ; class GFG { public static Boolean checkOverlapping ( ArrayList < Integer > a , ArrayList < Integer > b ) { if ( a . get ( 0 ) < b . get ( 0 ) ) { int temp = a . get ( 0 ) ; a . set ( 0 , b . get ( 0 ) ) ; b . set ( 0 , temp ) ; temp = a . get ( 1 ) ; a . set ( 1 , b . get ( 1 ) ) ; b . set ( 1 , temp ) ; } if ( b . get ( 0 ) <= a . get ( 0 ) && a . get ( 0 ) <= b . get ( 1 ) ) return true ; return false ; } public static int find ( ArrayList < Integer > a , int i ) { if ( a . get ( i ) == i ) { return i ; } a . set ( i , find ( a , a . get ( i ) ) ) ; return a . get ( i ) ; } public static Boolean union ( ArrayList < Integer > a , int x , int y ) { int xs = find ( a , x ) ; int ys = find ( a , y ) ; if ( xs == ys ) { return true ; } a . set ( ys , xs ) ; return false ; } public static Boolean checkNonOverlapping ( ArrayList < ArrayList < Integer > > arr , int n ) { ArrayList < Integer > dsu = new ArrayList < Integer > ( ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { dsu . add ( i ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( checkOverlapping ( arr . get ( i ) , arr . get ( j ) ) ) { if ( union ( dsu , i , j ) ) { return false ; } } } } return true ; } public static void main ( String [ ] args ) { ArrayList < ArrayList < Integer > > arr = new ArrayList < ArrayList < Integer > > ( ) ; arr . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 4 ) ) ) ; arr . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 2 ) ) ) ; arr . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 3 ) ) ) ; int n = arr . size ( ) ; if ( checkNonOverlapping ( arr , n ) ) { System . out . println ( " YES " ) ; } else { System . out . println ( " NO " ) ; } } }