Find the segment that overlaps with maximum number of segments | Java 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 ; Driver Code ; Given segments ; Size of segments array
import java . util . * ; class GFG { static void maxIntersection ( int segments [ ] [ ] , int N ) { int [ ] rvalues = new int [ N ] ; int [ ] lvalues = new int [ N ] ; for ( int i = 0 ; i < N ; ++ i ) { lvalues [ i ] = segments [ i ] [ 0 ] ; rvalues [ i ] = segments [ i ] [ 1 ] ; } Arrays . sort ( lvalues ) ; Arrays . sort ( rvalues ) ; int [ ] answer = { - 1 , - 1 } ; int numIntersections = 0 ; for ( int i = 0 ; i < N ; ++ i ) { int lesser = lower_bound ( rvalues , 0 , segments . length , segments [ i ] [ 0 ] ) ; int greater = Math . max ( 0 , N - ( upper_bound ( lvalues , 0 , segments . length , segments [ i ] [ 1 ] ) ) ) ; if ( ( N - lesser - greater ) >= numIntersections ) { answer = new int [ ] { segments [ i ] [ 0 ] , segments [ i ] [ 1 ] } ; numIntersections = ( N - lesser - greater ) ; } } System . out . print ( answer [ 0 ] + " ▁ " + answer [ 1 ] ) ; } static int lower_bound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } static int upper_bound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } public static void main ( String [ ] args ) { int segments [ ] [ ] = { { 1 , 4 } , { 2 , 3 } , { 3 , 6 } } ; int N = segments . length ; maxIntersection ( segments , N ) ; } }