Leetcode 1167: Minimum Cost to Connect Sticks

https://leetcode.com/problems/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^4
• 1 <= sticks[i] <= 10^4

Notes:

This question is a greedy question, every time we just need to put two the smallest ones together, until only one left.

Using priority_queue. But the default compare operator is less, so we need to explicitly define the operator as greater. Another detail is the top() function, not front(), even though its name is a queue...

See the code below:

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto &a : sticks) pq.push(a);
        int res = 0;
        while(pq.size() > 1) {
            int a = pq.top();
            pq.pop();
            a += pq.top();
            pq.pop();
            pq.push(a);
            res += a;
        }
        return res;
    }
};