Maximum number of intersections possible for any of the N given segments | java 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
import java . util . * ; class GFG { static int lower_bound ( int [ ] a , int low , int high , long element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } static int maximumIntersections ( int [ ] [ ] arr , int N ) { int count = 0 ; int [ ] L = new int [ N ] ; int [ ] R = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { L [ i ] = arr [ i ] [ 0 ] ; R [ i ] = arr [ i ] [ 1 ] ; } Arrays . sort ( L ) ; Arrays . sort ( R ) ; for ( int i = 0 ; i < N ; i ++ ) { int l = arr [ i ] [ 0 ] ; int r = arr [ i ] [ 1 ] ; int x = lower_bound ( L , 0 , N , l ) ; int y = N - lower_bound ( R , 0 , N , r + 1 ) ; int cnt = x + y ; cnt = N - cnt - 1 ; count = Math . max ( count , cnt ) ; } return count ; } public static void main ( String [ ] args ) { int arr [ ] [ ] = { { 1 , 6 } , { 5 , 5 } , { 2 , 3 } } ; int N = arr . length ; System . out . println ( maximumIntersections ( arr , N ) ) ; } }