patternMinor
DP for Weighted Interval Scheduling: why is sorting by finish time necessary?
Viewed 0 times
sortingwhynecessaryschedulingweightedintervalfinishtimefor
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#114748, answer score: 4
Revisions (0)
No revisions yet.