The `GreedySchedule`

algorithm we described for the class scheduling problem is not the only greedy strategy we could have tried. 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.

*Assume that all algorithms break ties arbitrarily (that is, in a manner that is completely out of your control).*

[Hint: Three of these algorithms are actually correct.]

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

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

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

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

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

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

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

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.

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