1167. Minimum Cost to Connect Sticks
https://www.lintcode.com/problem/minimum-cost-to-connect-sticks/description
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^41 <= sticks[i] <= 10^4
---
Intuition
Stick continues to add to ans till only 1 remains.
If we take larger sticks in the beginning, ans will increase too much
Take greedy approach - always the 2 min sticks
After merging, we need to find 2 min considering the merged stick
Need a data structure which will give min, and allow inserting back => min priority queue
---
Time - O(N log N)
Space - O(N)
---
