Find if there exists a direction for ranges such that no two range intersect | Javascript 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
let MAX = 100001 ; class interval { constructor ( ) { this . l = this . r = this . v = 0 ; } } function isPossible ( range , N ) { let test = new Array ( N ) ; for ( let 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 ] ; } test . sort ( function ( a , b ) { return ( a . v < b . v ? 1 : 0 ) ; } ) ; for ( let i = 0 ; i < N ; i ++ ) { let count = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) count [ i ] = 0 ; let current_velocity = test [ i ] . v ; let j = i ; while ( j < N && test [ j ] . v == current_velocity ) { for ( let k = test [ j ] . l ; k <= test [ j ] . r ; k ++ ) { count [ k ] ++ ; if ( count [ k ] >= 3 ) return false ; } j ++ ; } i = j - 1 ; } return true ; } let range = [ [ 1 , 2 , 3 ] , [ 2 , 5 , 1 ] , [ 3 , 10 , 1 ] , [ 4 , 4 , 1 ] , [ 5 , 7 , 10 ] ] let n = range . length ; if ( isPossible ( range , n ) ) document . write ( " " ) ; else document . write ( " " ) ;