$2.$ Class Scheduling: Recall the class scheduling problem described in lecture. We are given$$two arrays S$[1..$n$]$ and F$[1..$n$],$ where S$[$i$]<$ F$[$i$]$ for each i$,$ representing the start and$$finish times of n classes. Your goal is to find the largest number of classes you can take$$without ever taking two classes simultaneously. For each of the following greedy algorithms,$$either prove $($briefly explain why$)$ 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$).$ Exactly three of these greedy strategies actually work.$($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$.$