Maximum points covered after removing an Interval | Function To find the required interval ; Total Count of covered numbers ; Array to store numbers that occur exactly in one interval till ith interval ; Calculate New count by removing all numbers in range [ l , r ] occurring exactly once ; Driver code
def solve ( interval , N , Q ) : NEW_LINE INDENT Mark = [ 0 for i in range ( Q ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT l = interval [ i ] [ 0 ] - 1 NEW_LINE r = interval [ i ] [ 1 ] - 1 NEW_LINE for j in range ( l , r + 1 ) : NEW_LINE INDENT Mark [ j ] += 1 NEW_LINE DEDENT DEDENT count = 0 NEW_LINE for i in range ( Q ) : NEW_LINE INDENT if ( Mark [ i ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT count1 = [ 0 for i in range ( Q ) ] NEW_LINE if ( Mark [ 0 ] == 1 ) : NEW_LINE INDENT count1 [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , Q ) : NEW_LINE INDENT if ( Mark [ i ] == 1 ) : NEW_LINE INDENT count1 [ i ] = count1 [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT count1 [ i ] = count1 [ i - 1 ] NEW_LINE DEDENT DEDENT maxindex = 0 NEW_LINE maxcoverage = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT l = interval [ i ] [ 0 ] - 1 NEW_LINE r = interval [ i ] [ 1 ] - 1 NEW_LINE elem1 = 0 NEW_LINE if ( l != 0 ) : NEW_LINE INDENT elem1 = count1 [ r ] - count1 [ l - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT elem1 = count1 [ r ] NEW_LINE DEDENT if ( count - elem1 >= maxcoverage ) : NEW_LINE INDENT maxcoverage = count - elem1 NEW_LINE maxindex = i NEW_LINE DEDENT DEDENT print ( " Maximum ▁ Coverage ▁ is " , maxcoverage , " after ▁ removing ▁ interval ▁ at ▁ index " , maxindex ) NEW_LINE DEDENT interval = [ [ 1 , 4 ] , [ 4 , 5 ] , [ 5 , 6 ] , [ 6 , 7 ] , [ 3 , 5 ] ] NEW_LINE N = len ( interval ) NEW_LINE Q = 7 NEW_LINE solve ( interval , N , Q ) NEW_LINE