1
$\begingroup$

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 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?

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.