Practice › Heap & Priority Queue
Minimum Cost to Connect Ropes
Easy · Heap & Priority Queue · Asked at Amazon, Microsoft, Goldman Sachs, TCS, Infosys
Connecting two ropes of lengths x and y costs x + y and gives one rope of length x + y. Print the minimum total cost to connect all the ropes into one.
Input
First line: n. Second line: n space-separated integers.
Output
The minimum cost.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ len[i] ≤ 10^4
Always connect the two shortest ropes (like building a Huffman tree). Use a min-heap and 64-bit sums.
Example 1
Input
4 4 3 2 6
Output
29
Example 2
Input
1 7
Output
0
Hints
- A rope that is joined early is counted again in every later join, so short ropes should be joined first.
- Repeatedly take the two shortest ropes from a min-heap, add their sum to the cost, and push the new rope back.
Approach
Greedy, the same idea as Huffman coding. Put all lengths in a min-heap. While more than one rope remains, pop the two smallest x, y, add x + y to the cost and push x + y. Long ropes are joined last, so they are counted the fewest times. The total can exceed 2^31 — use 64-bit.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<long long, vector<long long>, greater<long long>> pq;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
pq.push(x);
}
long long cost = 0;
while (pq.size() > 1) {
long long x = pq.top();
pq.pop();
long long y = pq.top();
pq.pop();
cost += x + y;
pq.push(x + y);
}
cout << cost << "\n";
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
heap = data[1:]
heapq.heapify(heap)
cost = 0
while len(heap) > 1:
x = heapq.heappop(heap)
y = heapq.heappop(heap)
cost += x + y
heapq.heappush(heap, x + y)
print(cost)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
PriorityQueue<Long> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) pq.add(sc.nextLong());
long cost = 0;
while (pq.size() > 1) {
long x = pq.poll(), y = pq.poll();
cost += x + y;
pq.add(x + y);
}
System.out.println(cost);
}
}Solve Minimum Cost to Connect Ropes online · All practice problems