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?

  • 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