Given sorted file lengths, always merge the two smallest first (min-heap strategy). This greedy method minimizes total weighted merge cost and is analogous to Huffman coding construction.
int optimalMerge(vector<int>& files) {
priority_queue<int, vector<int>, greater<int>> pq(files.begin(), files.end());
int cost = 0;
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
int c = a + b;
cost += c;
pq.push(c);
}
return cost;
}Merge the two smallest files first at each step.
Min-heap provides efficient repeated extraction of smallest elements.
Same structural idea as building optimal prefix-code trees.
Quiz coming soon for this algorithm.