Check if given intervals can be made non | C # 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
using System ; using System . Collections . Generic ; class GFG { static bool checkOverlapping ( List < int > a , List < int > b ) { if ( a [ 0 ] < b [ 0 ] ) { int 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 ; } static int find ( List < int > a , int i ) { if ( a [ i ] == i ) { return i ; } a [ i ] = find ( a , a [ i ] ) ; return a [ i ] ; } static bool union ( List < int > a , int x , int y ) { int xs = find ( a , x ) ; int ys = find ( a , y ) ; if ( xs == ys ) { return true ; } a [ ys ] = xs ; return false ; } static bool checkNonOverlapping ( List < List < int > > arr , int n ) { List < int > dsu = new List < int > ( ) ; 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 [ i ] , arr [ j ] ) ) { if ( union ( dsu , i , j ) ) { return false ; } } } } return true ; } static void Main ( ) { List < List < int > > arr = new List < List < int > > ( ) ; arr . Add ( new List < int > { 1 , 4 } ) ; arr . Add ( new List < int > { 2 , 2 } ) ; arr . Add ( new List < int > { 2 , 3 } ) ; int n = arr . Count ; if ( checkNonOverlapping ( arr , n ) ) { Console . WriteLine ( " YES " ) ; } else { Console . WriteLine ( " NO " ) ; } } }