> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/greedy/1167.-minimum-cost-to-connect-sticks.md).

# 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`

```cpp
// 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;
}
```

```cpp
// 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;
}
```