Find if there exists a direction for ranges such that no two range intersect | Python implementation of the approach ; Function that returns true if the assignment of directions is possible ; Structure to hold details of each interval ; 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 poreturn false ; Driver code
MAX = 100001 NEW_LINE def isPossible ( rangee , N ) : NEW_LINE INDENT test = [ [ 0 for x in range ( 3 ) ] for x in range ( N ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT test [ i ] [ 0 ] = rangee [ i ] [ 0 ] NEW_LINE test [ i ] [ 1 ] = rangee [ i ] [ 1 ] NEW_LINE test [ i ] [ 2 ] = rangee [ i ] [ 2 ] NEW_LINE DEDENT test . sort ( key = lambda x : x [ 2 ] ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT count = [ 0 ] * MAX NEW_LINE current_velocity = test [ i ] [ 2 ] NEW_LINE j = i NEW_LINE while ( j < N and test [ j ] [ 2 ] == current_velocity ) : NEW_LINE INDENT for k in range ( test [ j ] [ 0 ] , test [ j ] [ 1 ] + 1 ) : NEW_LINE INDENT count [ k ] += 1 NEW_LINE if ( count [ k ] >= 3 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT j += 1 NEW_LINE DEDENT i = j - 1 NEW_LINE DEDENT return True NEW_LINE DEDENT rangee = [ [ 1 , 2 , 3 ] , [ 2 , 5 , 1 ] , [ 3 , 10 , 1 ] , [ 4 , 4 , 1 ] , [ 5 , 7 , 10 ] ] NEW_LINE n = len ( rangee ) NEW_LINE if ( isPossible ( rangee , n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT