Minimize segments required to be removed such that at least one segment intersects with all remaining segments | C ++ program for the above approach ; Function to find the minimum number of segments required to be deleted ; Stores the start and end points ; Traverse segments and fill the startPoints and endPoints ; Sort the startPoints ; Sort the startPoints ; Store the minimum number of deletions required and initialize with ( N - 1 ) ; Traverse the array segments [ ] ; Store the starting point ; Store the ending point ; Store the number of segments satisfying the first condition of non - intersection ; Store the number of segments satisfying the second condition of non - intersection ; Update answer ; Print the answer ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minSegments ( pair < int , int > segments [ ] , int n ) { int startPoints [ n ] , endPoints [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { startPoints [ i ] = segments [ i ] . first ; endPoints [ i ] = segments [ i ] . second ; } sort ( startPoints , startPoints + n ) ; sort ( endPoints , endPoints + n ) ; int ans = n - 1 ; for ( int i = 0 ; i < n ; i ++ ) { int f = segments [ i ] . first ; int s = segments [ i ] . second ; int leftDelete = lower_bound ( endPoints , endPoints + n , f ) - endPoints ; int rightDelete = max ( 0 , n - ( int ) ( upper_bound ( startPoints , startPoints + n , s ) - startPoints ) ) ; ans = min ( ans , leftDelete + rightDelete ) ; } cout << ans ; } int main ( ) { pair < int , int > arr [ ] = { { 1 , 2 } , { 5 , 6 } , { 6 , 7 } , { 7 , 10 } , { 8 , 9 } } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minSegments ( arr , N ) ; return 0 ; }