Maximum number of intersections possible for any of the N given segments | Python 3 program for the above approach ; Function to find the maximum number of intersections one segment has with all the other given segments ; Stores the resultant maximum count ; Stores the starting and the ending points ; Sort arrays points in the ascending order ; Traverse the array arr [ ] ; Find the count of segments on left of ith segment ; Find the count of segments on right of ith segment ; Find the total segments not intersecting with the current segment ; Store the count of segments that intersect with the ith segment ; Update the value of count ; Return the resultant count ; Driver Code
from bisect import bisect_left , bisect_right NEW_LINE def lower_bound ( a , low , high , element ) : NEW_LINE INDENT while ( low < high ) : NEW_LINE INDENT middle = low + ( high - low ) // 2 NEW_LINE if ( element > a [ middle ] ) : NEW_LINE INDENT low = middle + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = middle NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT def maximumIntersections ( arr , N ) : NEW_LINE INDENT count = 0 NEW_LINE L = [ 0 ] * N NEW_LINE R = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT L [ i ] = arr [ i ] [ 0 ] NEW_LINE R [ i ] = arr [ i ] [ 1 ] NEW_LINE DEDENT L . sort ( ) NEW_LINE R . sort ( ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT l = arr [ i ] [ 0 ] NEW_LINE r = arr [ i ] [ 1 ] NEW_LINE x = lower_bound ( L , 0 , N , l ) NEW_LINE y = N - lower_bound ( R , 0 , N , r + 1 ) NEW_LINE cnt = x + y NEW_LINE cnt = N - cnt - 1 NEW_LINE count = max ( count , cnt ) NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 1 , 6 ] , [ 5 , 5 ] , [ 2 , 3 ] ] NEW_LINE N = len ( arr ) NEW_LINE print ( maximumIntersections ( arr , N ) ) NEW_LINE DEDENT