minimum-cost-to-connect-sticks

< Previous 　　　　　　　　　　　　　　　　 Next >

1167. Minimum Cost to Connect Sticks (Medium)

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

Related Topics

[Array] [Greedy] [Heap (Priority Queue)]

Similar Questions

1. Minimum Cost to Merge Stones (Hard)

Hints

Hint 1

How many times does every stick contribute to the answer?

Hint 2

Some of the sticks will be used more than the others. Which sticks should be used the most/least?

Hint 3

The sticks with long lengths cost a lot so we should use these the least.

Hint 4

What if we keep merging the two shortest sticks?