Divide N segments into two non | Function to print the answer if it exists using the concept of merge overlapping segments ; Sort the indices based on their corresponding value in V ; Resultant array Initialise all the values in resultant array with '2' except the first index of ' indices ' which is initialised as '1' Initialise maxR to store the maximum of all right values encountered so far ; If the i - th index has any any point in common with the ( i - 1 ) th index classify it as '1' in resultant array and update maxR if necessary else we have found the breakpoint and we can exit the loop ; Driver Code
def printAnswer ( v , n ) : NEW_LINE INDENT indices = list ( range ( n ) ) NEW_LINE indices . sort ( key = lambda i : v [ i ] ) NEW_LINE res = [ 2 ] * n NEW_LINE res [ indices [ 0 ] ] = 1 NEW_LINE maxR = v [ indices [ 0 ] ] [ 1 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if maxR >= v [ indices [ i ] ] [ 0 ] : NEW_LINE INDENT res [ indices [ i ] ] = res [ indices [ i - 1 ] ] NEW_LINE maxR = max ( maxR , v [ indices [ i ] ] [ 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( " Not ▁ possible " ) NEW_LINE return NEW_LINE DEDENT print ( " ▁ " . join ( map ( str , res ) ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT v = [ [ 2 , 8 ] , [ 3 , 4 ] , [ 5 , 8 ] , [ 9 , 10 ] ] NEW_LINE n = len ( v ) NEW_LINE printAnswer ( v , n ) NEW_LINE DEDENT