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$. We are given an integer $k<n$, and we are allowed to choose $k$ arbitrary numbers. Suppose an interval is covered if it contains one of these $k$ numbers. With a $O(N\log N)$ algorithm, compute the maximum possible value of the total sum of the weights of the intervals we cover.
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 $8$ and $12$, so $(11, 13)$, $(11, 15)$ and $(7, 9)$ are covered, 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?