Maximum number of intersections possible for any of the N given segments | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumIntersections ( int arr [ ] [ 2 ] , int N ) { int count = 0 ; int L [ N ] , R [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { L [ i ] = arr [ i ] [ 0 ] ; R [ i ] = arr [ i ] [ 1 ] ; } sort ( L , L + N ) ; sort ( R , R + N ) ; for ( int i = 0 ; i < N ; i ++ ) { int l = arr [ i ] [ 0 ] ; int r = arr [ i ] [ 1 ] ; int x = lower_bound ( R , R + N , l ) - R ; int y = N - ( upper_bound ( L , L + N , r ) - L ) ; int cnt = x + y ; cnt = N - cnt - 1 ; count = max ( count , cnt ) ; } return count ; } int main ( ) { int arr [ ] [ 2 ] = { { 1 , 6 } , { 5 , 5 } , { 2 , 3 } } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximumIntersections ( arr , N ) ; return 0 ; }