Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $n$ intervals where each pair of intervals in the subset overlap (i.e. share a common value). Given an integer $k<n$, we would like to compute the maximum possible value of the total sum of all the weights covered when we choose k non-overlapping good subsets of intervals (i.e. no two of these subsets share an interval). How can you do this in an $O(N\log N)$ algorithm?
Sample input:
$n=6$, $k=2$
Intervals: $(-2, 2)$, $(3, 5)$, $(7, 9)$, $(9, 11)$, $(11, 13)$, $(11, 15)$
Weights: $w_1=0$, $w_2=6$, $w_3=10$, $w_4=8$, $w_5=12$, $w_6=14$
Expected output: $36$; formed by taking $\{(11, 13), (11, 15)\}$ and $\{(7, 9)\}$, so total weight is $12+14+10=36$
Some of my thoughts so far: This problems feel similar to the classic weighted interval scheduling problem, except instead we are trying to maximize the sum of overlapping interval sets rather than disjoint intervals. Additionally, we are trying to find the maximum for $k$ subsets rather than 1, so I can't see off the top of my head how the dynamic programming algorithm from the weighed interval scheduling problem can be used. Does anyone have any insight on this question?
