Minimum number of intervals to cover the target interval | Function to find the minimum number of intervals in the array A [ ] to cover the entire target interval ; Sort the array A [ ] in increasing order of starting point ; Insert a pair of INT_MAX to prevent going out of bounds ; Stores start of current interval ; Stores end of current interval ; Stores the count of intervals ; Iterate over all the intervals ; If starting point of current index <= start ; Update the value of start ; Increment the value of count ; If the target interval is already covered or it is not possible to move then break the loop ; If the entire target interval is not covered ; Return Answer ; Driver Code
def minimizeSegment ( A , X ) : NEW_LINE INDENT A . sort ( ) NEW_LINE INT_MAX = 2147483647 NEW_LINE A . append ( [ INT_MAX , INT_MAX ] ) NEW_LINE start = X [ 0 ] NEW_LINE end = X [ 0 ] - 1 NEW_LINE cnt = 0 NEW_LINE for i in range ( 0 , len ( A ) ) : NEW_LINE INDENT if ( A [ i ] [ 0 ] <= start ) : NEW_LINE INDENT end = max ( A [ i ] [ 1 ] , end ) NEW_LINE i = i + 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = end NEW_LINE cnt = cnt + 1 NEW_LINE if ( A [ i ] [ 0 ] > end or end >= X [ 1 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT if ( end < X [ 1 ] ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return cnt NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ [ 1 , 3 ] , [ 2 , 4 ] , [ 2 , 10 ] , [ 2 , 3 ] , [ 1 , 1 ] ] NEW_LINE X = [ 1 , 10 ] NEW_LINE print ( minimizeSegment ( A , X ) ) NEW_LINE DEDENT