Find if there exists a direction for ranges such that no two range intersect | Java implementation of the approach ; Structure to hold details of each interval ; Function that returns true if the assignment of directions is possible ; Sort the intervals based on velocity ; Test the condition for all intervals with same velocity ; If for any velocity , 3 or more intervals share a common point return false ; Driver code
import java . util . * ; class GFG { static int MAX = 100001 ; static class interval { int l , r , v ; } static class Sort implements Comparator < interval > { public int compare ( interval a , interval b ) { return ( a . v < b . v ? 1 : 0 ) ; } } static boolean isPossible ( int range [ ] [ ] , int N ) { interval test [ ] = new interval [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { test [ i ] = new interval ( ) ; test [ i ] . l = range [ i ] [ 0 ] ; test [ i ] . r = range [ i ] [ 1 ] ; test [ i ] . v = range [ i ] [ 2 ] ; } Arrays . sort ( test , new Sort ( ) ) ; for ( int i = 0 ; i < N ; i ++ ) { int count [ ] = new int [ MAX ] ; int current_velocity = test [ i ] . v ; int j = i ; while ( j < N && test [ j ] . v == current_velocity ) { for ( int k = test [ j ] . l ; k <= test [ j ] . r ; k ++ ) { count [ k ] ++ ; if ( count [ k ] >= 3 ) return false ; } j ++ ; } i = j - 1 ; } return true ; } public static void main ( String args [ ] ) { int range [ ] [ ] = { { 1 , 2 , 3 } , { 2 , 5 , 1 } , { 3 , 10 , 1 } , { 4 , 4 , 1 } , { 5 , 7 , 10 } } ; int n = range . length ; if ( isPossible ( range , n ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }