You are given n classes A$1,,$ An such that each Ai

is associated with $[$si$,$ fi$]$ where si and fi denote the start and the finishing time of Ai$.$ You are to select the maximum number of classes that can be scheduled in a single classroom such that no two activities

can be scheduled unless they do not have an overlapping period. Consider the following two

algorithms. Only one of them produces an optimal solution. For each algorithm, prove its

correctness or give a counter example to disprove it$.$

Algorithm $1$: Sort the activities according to their start times such that s$1<=$ s$2<=<=$ sn$.$

Consider activities A$1,$ A$2,$ An in this order, and schedule Ai to the room if it does not overlap with any class already scheduled.

Algorithm $2$: Sort the activities according to their finishing times such that f$1<=$ f$2<=<=$fn$.$ Consider activities A$1,$ A$2,$ An in this order, and schedule Ai to the room if it does not overlap with any class already scheduled.