Check if given intervals can be made non | C ++ implementation to check if the intervals can be non - overlapping 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkOverlapping ( vector < int > a , vector < int > b ) { if ( a [ 0 ] < b [ 0 ] ) { a . swap ( b ) ; } if ( b [ 0 ] <= a [ 0 ] <= b [ 1 ] ) return true ; return false ; } int find ( int a [ ] , int i ) { if ( a [ i ] == i ) return i ; a [ i ] = find ( a , a [ i ] ) ; return a [ i ] ; } bool Union ( 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 ; } bool checkNonOverlapping ( vector < vector < int > > arr , int n ) { int dsu [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) dsu [ i ] = 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 ; } int main ( ) { vector < vector < int > > arr = { { 1 , 4 } , { 2 , 2 } , { 2 , 3 } } ; int n = arr . size ( ) ; if ( checkNonOverlapping ( arr , n ) ) { cout << " YES " << endl ; } else { cout << " NO " << endl ; } return 0 ; }