Find the segment that overlaps with maximum number of segments | JavaScript program for the above approach ; Function to find the segment which overlaps with maximum number of segments ; ' L ' & ' R ' co - ordinates of all segments are stored in lvalues & rvalues ; Assign co - ordinates ; Co - ordinate compression ; Stores the required segment ; Stores the current maximum number of intersections ; Find number of ' R ' coordinates which are less than the ' L ' value of the current segment ; Find number of ' L ' coordinates which are greater than the ' R ' value of the current segment ; Segments excluding ' lesser ' and ' greater ' gives the number of intersections ; Update the current maximum ; Print segment coordinates ; Given segments ; Size of segments array
function lower_bound ( a , low , high , element ) { while ( low < high ) { var middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } function upper_bound ( a , low , high , element ) { while ( low < high ) { var middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } function maxIntersection ( segments , N ) { let rvalues = Array ( N ) . fill ( 0 ) ; let lvalues = Array ( N ) . fill ( 0 ) ; for ( i = 0 ; i < N ; ++ i ) { lvalues [ i ] = segments [ i ] [ 0 ] ; rvalues [ i ] = segments [ i ] [ 1 ] ; } lvalues . sort ( ( a , b ) => a - b ) ; rvalues . sort ( ( a , b ) => a - b ) ; let answer = [ - 1 , - 1 ] ; var numIntersections = 0 ; for ( var i = 0 ; i < N ; ++ i ) { var lesser = lower_bound ( rvalues , 0 , segments . length , segments [ i ] [ 0 ] ) ; var greater = Math . max ( 0 , N - ( upper_bound ( lvalues , 0 , segments . length , segments [ i ] [ 1 ] ) ) ) ; if ( ( N - lesser - greater ) >= numIntersections ) { answer = [ segments [ i ] [ 0 ] , segments [ i ] [ 1 ] ] ; numIntersections = ( N - lesser - greater ) ; } } document . write ( answer [ 0 ] + " " + answer [ 1 ] ) ; } var segments = [ [ 1 , 4 ] , [ 2 , 3 ] , [ 3 , 6 ] ] ; var N = segments . length ; maxIntersection ( segments , N ) ;