Which Rules Actually Hold

You are given start and finish times for n classes and want the largest set of classes that pairwise do not overlap. Each proposed algorithm below has the same shape: pick one class by the stated rule, throw away every class that conflicts with it, and recurse on what is left. Ties are broken by an adversary you do not control.

Which of these rules always return a maximum-size schedule? More than one is correct.

A

Pick the class with the shortest duration.

B

Pick the class that starts earliest.

C

Pick the class that finishes earliest.

D

Pick the class that starts latest.

E

Pick the class that conflicts with the fewest of the remaining classes.