Minimum Cost to Connect Sticks
There are n sticks with some lengths. The length of each stick is given in an array. The cost of connecting two sticks of lengths a and b is a + b. Find the minimum cost to connect all sticks.
Constraints:
- 1 <= n <= 10000
- 1 <= lengths[i] <= 10000
- The sum of all lengths will not exceed 10000
Examples:
Input: [1, 2, 3, 4]
Output: 10
Explanation: First, connect sticks of lengths 1 and 2, the cost is 3. Then connect sticks of lengths 3 and 4, the cost is 7. Finally, connect the two resulting sticks, the cost is 10. So the total cost is 3 + 7 + 10 = 20.
Solutions
Priority Queue
We use a priority queue to store the lengths of the sticks. We keep connecting the two sticks with the smallest lengths until only one stick is left. The cost of each connection is the sum of the lengths of the two sticks. We add this cost to the total cost and push the new stick back into the priority queue.
class Solution {
public: int connectSticks(vector<int>& sticks) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int stick : sticks) {
pq.push(stick);
}
int cost = 0;
while (pq.size() > 1) {
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
cost += a + b;
pq.push(a + b);
}
return cost;
}
}
;Follow-up:
What if the cost of connecting two sticks is not the sum of their lengths, but some other function of their lengths?
