Maximize count of intersecting line segments | C ++ 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 ] ) ; Push { 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 descending order ; Insert the first Y point from p ; Binary search to find the lower bound of p [ i ] . second ; If lower_bound doesn 't exist ; Insert p [ i ] . second into the set ; Erase the next lower _bound from the set ; Insert p [ i ] . second 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( int N , int X [ ] , int Y [ ] ) { vector < pair < int , int > > p ; for ( int i = 0 ; i < N ; i ++ ) { p . push_back ( { X [ i ] , Y [ i ] } ) ; } sort ( p . begin ( ) , p . end ( ) ) ; set < int , greater < int > > s ; s . insert ( p [ 0 ] . second ) ; for ( int i = 0 ; i < N ; i ++ ) { auto it = s . lower_bound ( p [ i ] . second ) ; if ( it == s . end ( ) ) { s . insert ( p [ i ] . second ) ; } else { s . erase ( * it ) ; s . insert ( p [ i ] . second ) ; } } return s . size ( ) ; } int main ( ) { int N = 3 ; int X [ ] = { 1 , 2 , 0 } ; int Y [ ] = { 2 , 0 , 1 } ; int maxintersection = solve ( N , X , Y ) ; cout << maxintersection ; }