Algorithms and Complexity – DP No.1

Given:
Set of $n$ intervals $[s_i,f_i]$ , each having weight $w_i$

Want:

Maximum weight subset of compatible intervals

Means:

we have:

$n$ requests labelled $1,2,\dots,n$
with each request specifying
- a start time $s_i$
- a finish time $f_i$
- a weight $w_i$
- Two intervals are compatible if they do not overlap
- The goal is to find a subset $S\{1,\dots,n\}$ that maximize the sum of the weights of selected intervals.

Solve:

Assume all requests are sorted in order of finish time: $f_1\leq f_2 \leq f_3 \leq \dots \leq f_n$

We say a request $i$ comes before a request $j$ if $i<j$
define $p(j)$ , for an interval $j$ , to be the largest index $i<j$ such that intervals $i$ and $j$ are disjoint
means $i$ is the leftmost interval that ends before $j$ begins, we define $p(j)=0$ if no request $i<j$ is disjoint from $j$ .

Prove:
Let $OPT$ be an optimal solution, ignoring for now we have no idea what $OPT$ is.
Claim:
Either interval $n$ (the last one) belongs to $OPT$ , or it doesn’t.

Claim 1: $n$ belongs to $OPT$ , then no interval indexed strictly between $p(n)$ and $n$ can belong to $OPT$ , and $OPT$ must include an optimal solution to the problem consisting of requests $\{1,\dots ,p(n)\}$ .

Thus $OPT-n$ is optimal for sub-instance $\{1,\dots ,p(n)\}$ of intervals that finish $\leq s_n$

Claim 2: $n$ does NOT belong to $OPT$ , then $OPT$ is equal to the optimal solution to the problem consisting of requests $\{1,…,n-1\}.$

Thus $OPT$ is optimal for sub-instance $\{1,…,n-1\}$

Now computes:

MWIS(n)
if n=0
  return 0 //optimum over empty set
else
  return max{ MWIS(n-1), MWIS(p(n))+w(n) }

Just like Fibonacci numbers, it runs in $T(n)=T(n-1)+T(n-2)+O(1)$
Reusing computation:

MWIS(n)
T  //array 1,...,n
T[0]=0
 for i = 1,…,n
T[i]= max{T[i],T[p(i)]+w(i)}
 return T[n]

Algorithm runs in $O(n)$ time
Took $O(n log n )$ to sort intervals and to compute $p(i)'s$ .

How to find optimal solution:

call MWIS(n) to compute array T
S   //empty set
i   //n
while i > 0
  if T[i]=T[p(i)]+w(i)
    add i to S
    i←p(n)
  else
    i←i-1

Note: array T contains the value of the optimal solution on the full instance.
Note: each state of DP takes $O(1)$ time, the algorithm runs $n$ iterations → $O(n)$

Algorithms and Complexity – DP No.1

Leave a Comment

Recent Posts