CODEWITHSUNDEEP
algorithm
CsIsFun
CsIsFun

Reputation: 151

Sorting different lines

I have been stuck on this problem. Can someone please help me solve this?

We are given n sorted lines of people with lengths l1, l2, ..., ln. The lines are all sorted by height. We want to merge all the lines into one sorted line. We can merge 2 lines at a time, which takes time that is proportional to the number of people in both lines.

Design an algorithm where we can choose the best order to merge all the lines for the least possible amount of time.

Upvotes: 2

Views: 141

Answers (1)

sve
sve

Reputation: 4356

Consider the greedy algorithm:

while line number > 1:
    take the shortest two lines  li, lj
    merge them

Is this the optimal solution? You see that the following facts are true:

  • if you know the merge tree (that is the tree which tells you that which pairs of lines were merged and when (deeper element are merged first and the tree is read from left to right)) we can see that an optimal solution is this one in which lines with small length have bigger depth. We can start from the leafs by filling the tree, bottom up, with the lines length sorted in ascending order.
  • that means the smallest two lines are at the leafs
  • changing the leaf order doesn't change the optimal solution
  • we can reorder the smallest lines to be first two leafs So we have found an optimal solution in which we pick merge the two line with smallest length. By induction we can continue like this.

You can implement this algorithm using min-priority queue. 

initialize min-priority queue q    
insert all line lengths in q
ans = 0
while q > 1:
    a = q.pop()
    b = q.pop()
    ans += a+b
    q.push(a+b)
return ans

Upvotes: 3

Related Questions