Optimal Merge Cost

Problem

Given the sizes of piles, return the minimum total cost of repeatedly merging piles in pairs, where merging two piles costs the sum of their sizes.

This is the optimal merge pattern, identical to Huffman coding: always merge the two smallest piles. Use a min-heap and accumulate each merge cost.

Hint

Merging the smallest piles first keeps large piles out of the total as long as possible.

case 1

in: [[1,2,3,4,5]]

expected: 33

case 2

in: [[5]]

expected: 0

case 3

in: [[1,1]]

expected: 2

case 4

in: [[10,20,30]]

expected: 90

case 5

in: [[2,2,2,2]]

expected: 16

Starter codePython

def optimal_merge_cost(piles):
    # Your code here
    pass

5 test cases · run your code against them in the editor