# Algorithm to find maximum sum over weighted overlapping intervals

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, we would like to compute the maximum possible value of the total sum of all the weights covered when we choose k good subsets of intervals. 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?

• Can an interval be a part of multiple subsets? Commented Dec 19, 2021 at 18:03
• @Inuyasah Yagami No. Look at the test case I mentioned, for instance. Commented Dec 19, 2021 at 18:05
• Does this answer your question? Maximize the sum of weights of covered intervals Commented Dec 21, 2021 at 1:36