3
$\begingroup$

Problem In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has a start time $s_i$, a finish time $f_i$, and a weight $w_i > 0$. We seek to find an optimal schedule — a subset $\cal{O}$ of non-overlapping jobs in $J$ with the maximum possible sum of weights.

Dynamic Programming Solution In almost all textbooks or materials I could get access to, a DP algorithm is given as follows: First all jobs are sorted in order of ascending finish time: $f_1\le f_2 \le \dots \le f_n$. Let $OPT(i)$ be the maximum total weight of non-overlapping jobs in $\{1,2, \cdots ,i\}$, $p_i$ be the largest index $j < i$ such that job $j$ and $i$ are compatible. Then we see that $$OPT(i) = \max\{{w_i + OPT(p_i), OPT(i-1)}\}$$

My question I think I could understand why this DP algorithm works. However I didn't see the necessasity for the sorting step. What if we sort the finish time in ascending order instead? As far as I can see, it's also correct.

$\endgroup$
2
$\begingroup$

Simple answer No, we cannot sort start time in ascending order to get a reasonable dynamic programming algorithm.

A counterexample

enter image description here

As illustrated above, we are given four jobs aligned in order of ascending start time, each labeled with its wight. Though some computation, we have $p_4=3$ and $OPT(4)=1+OPT(3)$. By definition, $OPT(3)$ equals to the optimal value in $\{1,2,3\}$. By selecting job $1$ and job $2$, $OPT(3)$ is maximized and is equal to $3$. Then the optimum subset of the four jobs would be $\{1,2,4\}$, which is not a compatible set.

Necessity for sorting finish time in ascending order: By sorting finishing time in ascending order, we ensure that for job $i$, $\{1,2,\dots, p_i\}$ is compatible with $i$ since they all finish before the start of $i$. But if we sort start time in ascending order instead, we cannot ensure that. As shown in above counterexample, $p_{4} = 3$, thus $\{1,2,\dots, p_4\}=\{1,2,3\}$ is not compatible with $4$. Suppose that $i$ is in the optimal solution $\mathcal{O}_i$ for $\{1,2,\dots, i\}$, then the optimal solution $\mathcal{O}_{p_i}$ for $\{1,2,\dots, p_i\}$ is also included in $\mathcal{O}_i$. specifically, we have $\mathcal{O}_{i} = \mathcal{O}_{p_i}\cup \{i\}$. Since we couldn't ensure that $i$ and $\mathcal{O}_{p_i}$ are compatible, we may get an invalid solution, which also can be seen from above counterexample.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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