I've been asked to do this task in an online assessment. I've passed, so my solution is supposedly correct, but I am unable to prove it. The task is:
Given a set of parts (array of integer part sizes), worker must put them all together. Parts are assembled in pairs. To put together two parts of sizes A and B worker needs A+B minutes. The resulting part's size is also A+B. Write a program to determine the minimum time required to put together given set of parts.
My solution was:
MinHeap h for p in parts: h.push(p) time = 0 while h.size() > 1: v1 = h.pop() v2 = h.pop() time += v1 + v2 ### assembly time h.push(v1 + v2) ### adding new part return time
This solution passed all tests.
Does this solution produce correct min time, and if yes, how to prove it?