Minimum time to assemble multipart object 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() &gt; 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.

Question:

Does this solution produce correct min time, and if yes, how to prove it?
Your solution (of greedily merging the two smallest objects available) is indeed correct. This problem is very classic and you can find it under the name 'rod connection' or 'rope connection'. Here (https://stackoverflow.com/questions/43715207/how-to-prove-this-greedy-algorithm-as-optimal-rod-connection) is the proof of optimality.