LC: 1167. Minimum Cost to Connect Sticks - spiralgo/algorithms GitHub Wiki

1167. Minimum Cost to Connect Sticks:

The Essence:

When choosing two sticks to connect from a set of sticks, we always need to choose 2 with the shortest lengths.

• Proof:

Let there be 3 sticks of length z>y=x.

Of the two ways the three can be connected, the inequality arises:

(x+y)+((x+y)+z)=2(x+y)+z < (x+z)+((x+z)+y)=2(x+z)+y

Details:

For always choosing the two shortest sticks, a priority queue can be used. The connected stick is inserted dynamically inserted back into the priority queue. Note that the procedure described is essentially a version of Huffman coding.