Variations of Activity Scheduling Algorithm

Question

I've been following Greedy algorithms in the textbook Jeff Erickson. Here is the following Question I was stuck in proving Proof of Correctness for the following variant of the standard Activity Selection problem.

For each of the following alternative greedy strategies, either prove that the resulting algorithm always constructs an optimal schedule, or describe a small input example for which the algorithm does not produce an optimal schedule.

(a) Choose the course x that ends last, discard classes that conflict with x, and recurse.

(b) Choose the course x that starts first, discard all classes that conflict with x, and recurse.

(c) Choose the course x that starts last, discard all classes that conflict with x, and recurse.

(d) Choose the course x with shortest duration, discard all classes that conflict with x, and recurse.

(e) Choose a course x that conflicts with the fewest other courses, discard all classes that conflict with x, and recurse.

(f) If no classes conflict, choose them all. Otherwise, discard the course with longest duration and recurse.

(g) If no classes conflict, choose them all. Otherwise, discard a course that conflicts with the most other courses and recurse.

(h) Let x be the class with the earliest start time, and let y be the class with the second earliest start time.

  • If x and y are disjoint, choose x and recurse on everything but x. 

  • If x completely contains y, discard x and recurse. 

  • Otherwise, discard y and recurse. 

(i) If any course x completely contains another course, discard x and recurse. Otherwise, choose the course y that ends last, discard all classes that conflict with y, and recurse.

I've been able to provide counter examples for (a),(b),(d) and I found that (c) is correct as it is just the the original problem if we imagine time running in reverse.

It will be very helpful if one provides the idea of proof of correctness for the remaining 2 correct strategies (as it's said in the text that out of all 9 strategies, 3 are correct).

Answer 1

The three Greedy strategies that work are (c),(h),(i).I'll prove them as follows, and for the remaining taking examples of 2-3 classes and tweaking them a bit, works as a contradictory example. Thanks, @D.W for providing a general strategy for proving correctness.

(c)
Claim $\textbf{1}.$ There is an optimal schedule that includes the course that starts last.
Proof: Let $x$ be the course that starts last. Let $S$ be any schedule that does not contain $x,$ and let $y$ be the last course in $S .$ Because $x$ starts last, we have $S[y]<S[x]$ Thus $F[i]<S[y]<S[x]$ for every other class $i$ in $S,$ which implies that $S^{\prime}=S-y+x$ is still a valid schedule, containing the same number of classes as $S .$ In particular, if $S$ is an optimal schedule, then $S^{\prime}$ is an optimal schedule containing $x$.
By the general greedy proof strategy described here and by using the above claim, by induction we can prove that this strategy works.

(h)
Claim $\textbf{2} .$ If $x$ and $y$ are disjoint, then every optimal schedule contains $x .$
Proof: If $x$ and $y$ are disjoint, then $F[x]<S[y],$ which implies that $F[x]<S[i]$ for all $i \neq x .$ Thus, if $S$ is any valid schedule that does not contain $x,$ then $S+x$ is a larger valid schedule. Thus, no optimal schedule excludes $x .$

Claim $\textbf{3} .$ If $x$ contains $y,$ there is an optimal schedule that excludes $x$
Proof: If $x$ contains $y,$ then every class that conflicts with $y$ also conflicts with $x$ Thus, for any valid schedule $S$ that contains $x,$ there is another valid schedule $S-x+y$ of the same size that excludes $x$

Claim $\textbf{4} .$ If $x$ and $y$ overlap, but $x$ does not contain $y,$ there is an optimal schedule that excludes $y$
Proof: Suppose $x$ and $y$ overlap, but $x$ does not contain $y .$ Then $x$ must end before $y$ ends, and therefore every class that conflicts with $x$ also conflicts with $y .$ Thus, for any valid schedule $S$ that contains $y,$ there is another valid schedule $S-y+x$ of the same size that excludes $y$.
By the general greedy proof strategy described here and by using the above claims, by induction we can prove that this strategy works.

(i)
Claim $\textbf{5} $. If any course $x$ contains another course $y,$ there is an optimal schedule that does not include $x$. Proof: Let $S$ be any valid schedule that contains $x .$ Then $S-x+y$ is another valid schedule of the same size.

Claim $\textbf{6} $. Suppose no course contains any other course. Then there is an optimal schedule containing the course that ends last.
Proof: If no course contains any other course, then the class that ends last is also the class that starts last. This claim now follows from Claim 1.
Hence, by the general greedy proof strategy described here and by using the above two claims, by induction we can prove that this strategy works.