Mid/Senior
Minimum Cost to Connect Sticks
You have some number of sticks with positive integer lengths, given as an array sticks, where sticks[i] is the length of the ith stick.
You can connect any two sticks of lengths x and y into one stick. The cost of this operation is x + y, and the resulting stick has length x + y.
Return the minimum total cost required to connect all sticks into one stick.
Example 1
Input
sticks = [2,4,3]Output
14Connect sticks of lengths 2 and 3 for cost 5, then connect lengths 4 and 5 for cost 9, for a total cost of 14.
Example 2
Input
sticks = [1,8,3,5]Output
30One optimal sequence costs 4, then 9, then 17, for a total cost of 30.
Constraints
- 1 <= sticks.length <= 10^4
- 1 <= sticks[i] <= 10^4