Minimize cost to empty given array where cost of removing an element is its absolute difference with Time instant | Python3 program for the above approach ; Function to find the minimum cost to delete all array elements ; Sort the input array ; Store the maximum time to delete the array in the worst case ; Store the result in cost [ ] [ ] table ; Base Case ; Store the minimum of all cost values of the previous index ; Iterate from range [ 1 , n ] using variable i ; Update prev ; Iterate from range [ 1 , m ] using variable j ; Update cost [ i ] [ j ] ; Update the prev ; Store the minimum cost to delete all elements ; Find the minimum of all values of cost [ n ] [ j ] ; Print minimum cost ; Driver Code ; Function Call
INF = 10000 NEW_LINE def minCost ( arr , n ) : NEW_LINE INDENT arr = sorted ( arr ) NEW_LINE m = 2 * n NEW_LINE cost = [ [ INF for i in range ( m + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE cost [ 0 ] [ 0 ] = 0 NEW_LINE prev = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT prev = cost [ i - 1 ] [ 0 ] NEW_LINE for j in range ( 1 , m + 1 ) : NEW_LINE INDENT cost [ i ] [ j ] = min ( cost [ i ] [ j ] , prev + abs ( j - arr [ i - 1 ] ) ) NEW_LINE prev = min ( prev , cost [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT minCost = INF NEW_LINE for j in range ( 1 , m + 1 ) : NEW_LINE INDENT minCost = min ( minCost , cost [ n ] [ j ] ) NEW_LINE DEDENT print ( minCost ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 2 , 4 , 4 , 5 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE minCost ( arr , N ) NEW_LINE DEDENT