Minimum Cost to Connect Sticks

Similar Problems:

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3] Output: 14

Example 2:

Input: sticks = [1,8,3,5] Output: 30

Constraints:

- 1 <= sticks.length <= 10^4
- 1 <= sticks[i] <= 10^4

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/minimum-cost-to-connect-sticks // Basic Ideas: min heap // cost = (n-1)*l[0]+(n-1)*l[1]+(n-2)*l[2]+(n-3)*l[3]....+ l[n-1] // Complexity: O(n*log(n)), Space O(n) // min heap type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { res := (*h)[len(*h)-1] *h = (*h)[0:len(*h)-1] return res } func connectSticks(sticks []int) int { h := &IntHeap{} heap.Init(h) for _, v := range sticks { heap.Push(h, v) } res := 0 for h.Len() > 1 { n1 := heap.Pop(h).(int) n2 := heap.Pop(h).(int) res += n1+n2 heap.Push(h, n1+n2) } return res }