Minimize segments required to be removed such that at least one segment intersects with all remaining segments | Java 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static class Pair { int first ; int second ; Pair ( int first , int second ) { this . first = first ; this . second = second ; } } public static int lower_bound ( int arr [ ] , int key ) { int l = - 1 , r = arr . length ; while ( l + 1 < r ) { int m = ( l + r ) >>> 1 ; if ( arr [ m ] >= key ) r = m ; else l = m ; } return r ; } public static int upper_bound ( int arr [ ] , int key ) { int l = - 1 , r = arr . length ; while ( l + 1 < r ) { int m = ( l + r ) >>> 1 ; if ( arr [ m ] <= key ) l = m ; else r = m ; } return l + 1 ; } static void minSegments ( Pair segments [ ] , int n ) { int startPoints [ ] = new int [ n ] ; int endPoints [ ] = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { startPoints [ i ] = segments [ i ] . first ; endPoints [ i ] = segments [ i ] . second ; } Arrays . sort ( startPoints ) ; Arrays . sort ( endPoints ) ; 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 , f ) ; int rightDelete = Math . max ( 0 , n - ( int ) ( upper_bound ( startPoints , s ) ) ) ; ans = Math . min ( ans , leftDelete + rightDelete ) ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { Pair arr [ ] = { new Pair ( 1 , 2 ) , new Pair ( 5 , 6 ) , new Pair ( 6 , 7 ) , new Pair ( 7 , 10 ) , new Pair ( 8 , 9 ) } ; int N = arr . length ; minSegments ( arr , N ) ; } }