0
$\begingroup$

I'm reading a dynamic programming algorithm to the weighted interval scheduling problem. There are $n$ intervals, each has a start time $s_i$, a finishing time $f_i$ and a value $v_i$. The goal is to find a subset of intervals with the maximum total of values. Let $p(j)=i$ be the left-most interval $i$ that finishes before interval $j$ begins.

Can you explain this reasoning:

"If interval $n$ (the last one) belongs to an optimal solution $O$, then $O$ must include an optimal solution to the problem consisting of intervals $\{1,...,p(n)\}$ -- for if it didn't, we could replace $O$'s choice of intervals from $\{1,...,p(n)\}$ with a better one, with no danger of overlapping n."

In particular, I don't understand how I can "replace the optimal solution with a better one". Thank you.

Below is the scanned copy of what I'm reading. My question is about the last sentence.

scanned copy of the reading

  • 0
    Not sure if my answer is exactly what you're looking for, but let me know if you could use any more help.2012-06-19

1 Answers 1

0

When a dynamic programming approach applies to a problem of interest, showing the optimal subproblem property typically boils down to the following approach:

a) Name an optimal solution to the original problem

b) Consider a generic subproblem and name its solution

c) Suppose the solution from part b) does not sit inside of the solution from part a) and derive a contradiction

There is a slight abuse of notation in the last paragraph; the set $\{ 1, ..., p(n) \}$ does not consist of requests, but rather request indices. Now, since $p(n)$ is the maximal index $j$ such that intervals $j$ and $n$ are disjoint, the case $n\in \mathcal{O}$ leads us to consider the subproblem of interval scheduling for requests $\{ f_1, ... , f_{p(n)} \}.$

Let $\{ i_1, i_2 , ..., i_n, n \}$ be an optimal interval schedule for the original problem and $\{ j_1, ... , j_m, \}$ be an optimal interval schedule for the aforementioned subproblem. This means that $\displaystyle\sum_{k=1}^n v_{i_k} \le \displaystyle\sum_{k=1}^m v_{j_k}.$ Suppose that there exists $k$ ($1\le k \le m$) such that $j_k \notin \mathcal{O}.$ Since $j_m \le p(n)$ (this is immediate by our statement of the subproblem), we can consider the interval schedule $\{ j_1, ... , j_m, n \}$ for our original problem. Using the previous inequality, we see that $(\displaystyle\sum_{k=1}^n v_{i_k} ) +n \le (\displaystyle\sum_{k=1}^m v_{j_k}) +n,$ contradicting the optimality of $\{ i_1, i_2 , ..., i_n, n \}.$

  • 0
    For instance, in the solution I provided, the name of the optimal solution is $\{ i_1, i_2 , ..., i_n , n \}.$2012-06-23