Maximize the sum of interval lengths in intersection of interval sets

Question

We have n sets of intervals, where each set S_i is consists of non-overlapping intervals [A_i_1, B_i_1], [A_i_2, B_i_2], ...

Given a positive integer k (where k <= n), we want to find k sets out of the n sets that maximize the sum of the length of the intervals formed by taking intersections of those k sets. Here, taking intersections of the k sets means we form a set of intervals [C_1, D_1], [C_2, D_2], ..., where a [C_j, D_j] is contained in each of the k interval sets, meaning that for each interval set i, [C_j, D_j] is contained in some [A_i_l, B_i_l].

For example, we have 3 sets of intervals

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

and we want to find 2 sets that maximize their intersections, so here the answer would be Set 1, Set 2 where the intersection is [1, 2], [3, 5], and another answer is Set 2, Set 3 where the intersection is [1, 2], [3, 4], [5, 6].

This problem came from a practical situation where I want to find a maximum set of dates from several sets of dates.

Answer 1

This paper shows that this is NP-hard.