Maximize count of intersecting line segments | Python3 program for the above approach ; Function to find the maximum number of intersecting line segments possible ; Stores pairs of line segments { X [ i ] , Y [ i ] ) ; Push { X [ i ] , Y [ i ] } into p ; Sort p in ascending order of points on X number line ; Stores the points on Y number line in descending order ; Insert the first Y pofrom p ; Binary search to find the lower bound of p [ i ] [ 1 ] ; If lower_bound doesn 't exist ; Insert p [ i ] [ 1 ] into the set ; Erase the next lower _bound from the set ; Insert p [ i ] [ 1 ] into the set ; Return the size of the set as the final result ; Driver Code ; Given Input ; Function call to find the maximum number of intersecting line segments
from bisect import bisect_left NEW_LINE def solve ( N , X , Y ) : NEW_LINE INDENT p = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT p . append ( [ X [ i ] , Y [ i ] ] ) NEW_LINE DEDENT p = sorted ( p ) NEW_LINE s = { } NEW_LINE s [ p [ 0 ] [ 1 ] ] = 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT arr = list ( s . keys ( ) ) NEW_LINE it = bisect_left ( arr , p [ i ] [ 1 ] ) NEW_LINE if ( it == len ( s ) ) : NEW_LINE INDENT s [ p [ i ] [ 1 ] ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT del s [ arr [ it ] ] NEW_LINE s [ p [ i ] [ 1 ] ] = 1 NEW_LINE DEDENT DEDENT return len ( s ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE X = [ 1 , 2 , 0 ] NEW_LINE Y = [ 2 , 0 , 1 ] NEW_LINE maxintersection = solve ( N , X , Y ) NEW_LINE print ( maxintersection ) NEW_LINE DEDENT