Question

Prove that the Task Selection algorithm is correct, meaning that it always returns a maximum set of non-overlapping tasks. (Hint: use a replacement-type argument similar to that used in proving correctness of Kruskal’s algorithm.)

Answer 1

Explanation :

Assume that  each task t has a positive duration i.e., f(t) − s(t) > 0. Let t₁, . . . , t_n be the tasks selected by TSA(Task Selection Algorithm) , where the tasks are in the order in which they were selected (i.e. increasing start times). Let T_opt be a maximum set of non-overlapping tasks. Let k be the least integer for which t_k T_opt. Thus t₁, . . . , t_k−1 ∈ T_opt.

Claim: t₁, . . . , t_k−1 are the only tasks in T_opt that start at or before t_k−1. Suppose, by way of contradiction, that there is a task t in T_opt that starts at or before t_k−1, and t   t_i , i = 1, . . . , k − 1. Since t does not overlap with any of these ti , either t is executed before t₁ starts, in between two tasks t_i and t_i+1, where 1 ≤ i < k − 1. In the former case, ASA would have selected t instead of t₁ since f(t) < f(t₁). In the latter case, ASA would have selected t instead of t_i+1, since both start after t_i finishes, but f(t) < f(t_i+1). This proves the claim.

Hence, the first k − 1 tasks (in order of start times) in T_opt are identical to the first k − 1 tasks selected by TSA. Now let t be the k th task in T_opt. Since TSA selected t_k instead of t as the k th task to add to the output set, it follows that f(t_k) ≤ f(t). Moreover, since both tasks begin after t_k−1 finishes, the set T_opt2 − t + t_k is a non-overlapping set of tasks (since t_k finishes before t, and starts after t_k−1 finishes) with the same size as T_opt. Hence, T_opt2 is also optimal, and agrees with the TSA output in the first k tasks.

By repeating the above argument we are eventually led to an optimal set of tasks whose first n tasks coincide with those returned by TSA. Moreover, this optimal set could not contain any other tasks. For example, if it contained an additional task t, then t must start after tn finishes. But then the algorithm would have added t (or an alternate task that started after the finish of t_n) to the output, and would have produced an output of size at least n+ 1. Therefore, there is an optimal set of tasks that is equal to the output set of TSA, meaning that TSA is a correct algorithm.

For Better understanding (In image form) :