1167. Minimum Cost to Connect Sticks

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

// Priority_Queue (Min heap)
int connectSticks(vector<int>& sticks) { // time: O(log(n!)); space: O(n)
    priority_queue<int, vector<int>, greater<int> > pq(sticks.begin(), sticks.end());
    int res = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        pq.push(a + b);
        res += (a + b);
    }
    return res;
}

// Greedy Method
// InputSet: [right, numSticks)
// ResultSet: [left, numResults)
bool getMin(vector<int>& sticks, int& num, int& left, int& right, int numSticks, int numResults) {
    bool f = right < numSticks, s = left < numResults;
    if (f && s) num = (sticks[left] <= sticks[right]) ? sticks[left++] : sticks[right++];
    else if (f) num = sticks[right++];
    else if (s) num = sticks[left++];
    return f || s;
}
int connectSticks(vector<int>& sticks) { // time: O(nlogn); space: O(n)
    int numSticks = sticks.size(), numResults = 0, left = 0, right = 0;
    sort(sticks.begin(), sticks.end());
    int res = 0, min1 = 0, min2 = 0;
    while (getMin(sticks, min1, left, right, numSticks, numResults) && 
           getMin(sticks, min2, left, right, numSticks, numResults)) {
        res += sticks[numResults++] = min1 + min2;
    }
    return res;
}