[LeetCode] Minimum Cost to Connect Sticks

1167. Minimum Cost to Connect Sticks

You have some number of sticks with positive integer lengths. These lengths are 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 by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int connectSticks(vector<int>& sticks) {
int res = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for(auto n : sticks) pq.push(n);
while(pq.size() != 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
res += a + b;
pq.push(a + b);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/19/PS/LeetCode/minimum-cost-to-connect-sticks/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.