Consider the following scheduling problem: for a certain lecture room, we are given the start and end times of a set of classes that could be assigned to the room. We wish to create a schedule that maximizes the number of classes assigned to the room, so that none of those classes "overlap" in time. (The remaining classes will be assigned to other rooms.) Note that classes whose times intersect only at their boundaries (start/finish times) do not overlap, and that there may be more than one optimal schedule. A bold 376 classmate claims to have devised a greedy algorithm that always produces an optimal schedule, which is shown below. 1: function Schedule(X) 2: Y empty list 3: for each c in X, in ascending order by start time (breaking ties arbitrarily) do 4: if c does not overlap with any class in Y then 5: append c to Y 6: return Y Consider the following set of potential classes for the room: (a) What schedule will the above algorithm return when given the above list of classes? Is this schedule optimal? Explain why or why not. (b) Provide a set of class times for which the above algorithm returns a suboptimal schedule, and give an optimal schedule for comparison. (c) Let's modify the above algorithm so that it instead considers the classes in order by their finish times, still in ascending order. Let Y=[c1,c2,,ck] denote the output of the modified algorithm, and let S= [s1,s2,,sm] be some arbitrary optimal schedule (in ascending order by time). Note that km because both Y and S are valid schedules, and S is an optimal one. Prove by induction that for every ik, class ci finishes no later than si finishes. In other words, prove that ci.fsi.f, where the .f suffix denotes the finishing time of a class. (Your proof may also use suffix.s for a class's starting time, and you may assume that every class c has nonzero length, i.e., c.s