最大化間隔的長度之和中的間隔套

Question

我們有n集間隔，其中每個設定S_i是交集包含非重疊間隔[A_i_1, B_i_1]，[A_i_2, B_i_2]的，...

給定一個正整數k（其中k <= n），我們希望找到k集合中的n集合，其最大化通過對這些集合的交集形成的區間長度的總和。這裏，取k套交叉意味着我們形成了一套間隔[C_1, D_1]，[C_2, D_2]，...，其中一個[C_j, D_j]被包含在每個k區間集，這意味着每個時間間隔設置i，[C_j, D_j]包含在一些[A_i_l, B_i_l]的。

例如，我們有3套間隔

Set 1: [1, 2] [3, 5] 
Set 2: [1, 2] [3, 6] 
Set 3: [1, 2] [3, 4] [5, 6] 

的，我們想找到2臺，最大限度地提高它們的交點，所以這裏的答案會是Set 1，Set 2交匯的地方是[1, 2], [3, 5]，和另外一個答案是Set 2，Set 3其中交點是[1, 2],[3, 4],[5, 6]。

這個問題來自實際情況，我想從幾組日期中找到最大的一組日期。

Answer 1

這paper表明這是NP難。