DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Question

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.

Answer 1

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

A counterexample

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 by 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.

Answer 2

Sorting step is necessary however like you mentioned, it can be sorted in ascending order too. Just that the traversal will have to be from end to beginning then (instead of descending sort which has beginning to end traversal)