2
$\begingroup$

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.

Question:

Does this solution produce correct min time, and if yes, how to prove it?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.