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

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.

## 1 Answer

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.