間隔のnセットがあり、各セットS_iは重複しない間隔[A_i_1, B_i_1]、[A_i_2, B_i_2]、 ...で構成されています。
正の整数k(ここで) が与えられた場合、これらのセットの交点を取ることによって形成される間隔の長さの合計を最大化するセットをセットk <= nから見つけたいと考えています。ここで、セットの共通部分を取るということは、間隔、、...のセットを形成することを意味します。ここで、 aは各間隔セットに含まれています。knkk[C_1, D_1][C_2, D_2][C_j, D_j]ki[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]。
この問題は、いくつかの日付セットから最大の日付セットを見つけたいという実際的な状況から発生しました。