Find the segment that overlaps with maximum number of segments | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maxIntersection ( int segments [ ] [ 2 ] , int N ) { vector < int > rvalues ( N ) , lvalues ( N ) ; for ( int i = 0 ; i < N ; ++ i ) { lvalues [ i ] = segments [ i ] [ 0 ] ; rvalues [ i ] = segments [ i ] [ 1 ] ; } sort ( lvalues . begin ( ) , lvalues . end ( ) ) ; sort ( rvalues . begin ( ) , rvalues . end ( ) ) ; pair < int , int > answer = { -1 , -1 } ; int numIntersections = 0 ; for ( int i = 0 ; i < N ; ++ i ) { int lesser = lower_bound ( rvalues . begin ( ) , rvalues . end ( ) , segments [ i ] [ 0 ] ) - rvalues . begin ( ) ; int greater = max ( 0 , N - ( int ) ( upper_bound ( lvalues . begin ( ) , lvalues . end ( ) , segments [ i ] [ 1 ] ) - lvalues . begin ( ) ) ) ; if ( ( N - lesser - greater ) >= numIntersections ) { answer = { segments [ i ] [ 0 ] , segments [ i ] [ 1 ] } ; numIntersections = ( N - lesser - greater ) ; } } cout << answer . first << " ▁ " << answer . second ; } int main ( ) { int segments [ ] [ 2 ] = { { 1 , 4 } , { 2 , 3 } , { 3 , 6 } } ; int N = sizeof ( segments ) / sizeof ( segments [ 0 ] ) ; maxIntersection ( segments , N ) ; }