Maximize count of intersecting line segments | Java 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 ] ) ; Add { 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 ascending order ; Insert the first Y point from p ; Binary search to find the floor value of p . get ( i ) [ 1 ] ; If floor value doesn 't exist ; Insert p . get ( i ) [ 1 ] into the set ; Erase the next floor value from the set ; Insert p . get ( 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static int solve ( int N , int X [ ] , int Y [ ] ) { ArrayList < int [ ] > p = new ArrayList < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { p . add ( new int [ ] { X [ i ] , Y [ i ] } ) ; } Collections . sort ( p , ( p1 , p2 ) -> { if ( p1 [ 0 ] != p2 [ 0 ] ) return p1 [ 0 ] - p2 [ 0 ] ; return p1 [ 1 ] - p2 [ 1 ] ; } ) ; TreeSet < Integer > s = new TreeSet < > ( ) ; s . add ( p . get ( 0 ) [ 1 ] ) ; for ( int i = 0 ; i < N ; i ++ ) { Integer it = s . floor ( p . get ( i ) [ 1 ] ) ; if ( it == null ) { s . add ( p . get ( i ) [ 1 ] ) ; } else { s . remove ( it ) ; s . add ( p . get ( i ) [ 1 ] ) ; } } return s . size ( ) ; } public static void main ( String [ ] args ) { int N = 3 ; int X [ ] = { 1 , 2 , 0 } ; int Y [ ] = { 2 , 0 , 1 } ; int maxintersection = solve ( N , X , Y ) ; System . out . println ( maxintersection ) ; } }