-1
$\begingroup$

Suppose we have $n$ weighted intervals (positive integer weights). Can we find the subset of these intervals which are non overlapping and has maximum sum weight? What is the most efficient algorithm that does this?

More formally, suppose that we have intervals $I = \{[a_i, b_i]\}$ for $1\le i\le n$ and $w_i$ which is the assigned weight to each interval. The goal is to find the subset of $S \subset I$ which satisfies $i\ne j: I_i\cap I_j = \emptyset$ and $\sum_{I_i \in S} w_i$ is minimised: $$\arg\min_S \Big\{\sum_{I_i \in S} w_i \Big\}$$

$\endgroup$
2

1 Answer 1

1
$\begingroup$

I think I might have a solution for this.

We build a graph $G=(V,E)$ consisting of nodes $V=\{a_1, ..., a_n, b_1, ... , b_n\}$ and edges are consisted two separate sets $E = E_1 \cup E_2$, which are defined as: $E_1 = \{(a_i,b_i)\}$ and assign $w_i$ as weights to these edges. $E_2 = \{(b_i,a_j) | b_i < a_j \}$ and assign $0$ as weight to these edges.

Lemma: This graph is a DAG. Because every node is only connected to a node that has a strictly bigger value. So there is an absolute ordering for the graph.

Lemma 2: Any non-overlapping subset of intervals corresponds to a path in the graph $G$ and vice versa. Moreover the length of the path equals to the sum of the weights of the intervals.

a) subset to path: Each subset of intervals will be equivalent to choosing their corresponding edges in $E_1$ and then these edges can be connected to each other using the edges in $E_2$. Because edges in $E_2$ have zero weight the total weight of the path is equal to sum of the edges in $E_1$ which is the sum of weights of the intervals.

b) path to subset: Because the graph is a DAG the path doesn't contain two of the same edge. Moreover if two edges $e_1$ and $e_2$ are on the path the cannot overlap. Therefore any path will be equivalent to a non-overlaying set of intervals. Also the sum of the edge weights in $E_1$ is clearly equal to the sum of interval weights in the subset

Therefore, the problem of maximum non-overlaying subset is transformed to maximal path.

In a DAG there is an algorithm of $\mathcal{O}(N+E)$ that computes the longest path. Now since we might have added a quadratic number of edges this will be $\mathcal{O}(N^2)$ solution. The rest of the complexity (including the sorting part) will be lower.

$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.