Minimize segments required to be removed such that at least one segment intersects with all remaining segments | Pyhton3 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
from bisect import bisect_left , bisect_right NEW_LINE def minSegments ( segments , n ) : NEW_LINE INDENT startPoints = [ 0 for i in range ( n ) ] NEW_LINE endPoints = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT startPoints [ i ] = segments [ i ] [ 0 ] NEW_LINE endPoints [ i ] = segments [ i ] [ 1 ] NEW_LINE DEDENT startPoints . sort ( reverse = False ) NEW_LINE endPoints . sort ( reverse = False ) NEW_LINE ans = n - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT f = segments [ i ] [ 0 ] NEW_LINE s = segments [ i ] [ 1 ] NEW_LINE leftDelete = bisect_left ( endPoints , f ) NEW_LINE rightDelete = max ( 0 , n - bisect_right ( startPoints , s ) ) NEW_LINE ans = min ( ans , leftDelete + rightDelete ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 1 , 2 ] , [ 5 , 6 ] , [ 6 , 7 ] , [ 7 , 10 ] , [ 8 , 9 ] ] NEW_LINE N = len ( arr ) NEW_LINE minSegments ( arr , N ) NEW_LINE DEDENT