For the following alternative greedy algoriths for the class scheduling problem,
ID: 3828271 • Letter: F
Question
For the following alternative greedy algoriths for the class scheduling problem, either prove that the 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).
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.Explanation / Answer
The algorithm does not produce an oprimal schedule always. Consider that x, y and z are 3 classes such that y overlaps x and y overlaps z. But x and z are disjoint. In this case, x is discarded and z is also discarded, which is not optimal.