The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which encloses intervals from both child nodes. The goal is to minimize the sum of lengths of intervals in interior nodes.

Example. Input $I=\{[1,5], [7,9], [20,25]\}$

leaf nodes: $l_1 = [1,5], l_2 = [7,9], l_3=[20,25]$

interior nodes $i_1 = (l_1, l_2, [1,9]), i_2= (i_1, l_3,[1,25])$

Is this problem NP-hard?


closed as off-topic by Jeffε, Peter Shor , Marzio De Biasi, Kaveh, R B Mar 7 '16 at 6:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jeffε, Peter Shor , Marzio De Biasi, Kaveh, R B
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ You should be able to use dynamic programming to solve this in polynomial time. $\endgroup$ – Peter Shor Mar 6 '16 at 16:01
  • 3
    $\begingroup$ More precisely, you're asking for an alphabetical Huffman tree. $\endgroup$ – S. Pek Mar 6 '16 at 18:59
  • 3
    $\begingroup$ @S. Pek: this is not quite an alphabetical Huffman tree. If you join the intervals [1,3] and [4,5] (weights 2 and 1, respectively), you get [1,5] (weight 4). In an alphabetic Huffman tree, it would be weight 3. I have no idea whether this breaks any of the alphabetic Huffman tree algorithms. If the intervals were all touching, it would be an alphabetic Huffman tree. $\endgroup$ – Peter Shor Mar 6 '16 at 22:32