Consider this classic 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 offered in the room, so that none of them

overlap in time. (The remaining classes are assigned to other rooms.) Note that there may

be more than one optimal schedule!

A bold 376 classmate claims to have come up with an algorithm that will always produce an

optimal schedule, which works as follows:

What schedule will this algorithm return when given the above list of classes? Is it

optimal? Justify your answer.

(b) Provide a set of class times for which the above algorithm returns a

suboptimal

schedule,

and show an optimal schedule for comparison.

(c) Lets modify the above algorithm so that it instead sorts the classes by their

finish

times

(in ascending order). Let

Y

= [

c

1

,c

2

,

,c

k

] denote the final output of the algorithm,

and

S

= [

s

1

,s

2

,

,s

m

] denote an arbitrary optimal schedule.

Prove by induction that for every

i

k

, the finishing time of class

c

i

is no later than the

finishing time of class

s

i

. Then use this to prove that

k

=

m

i.e., schedule

Y

is optimal

(because it has the same number of classes as an optimal schedule).

4. Consider this classic 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 offered in the room, so that none of them overlap in time. (The remaining classes are assigned to other rooms.) Note that there may be more than one optimal schedule! A bold 376 classmate claims to have come up with an algorithm that will always produce an optimal schedule, which works as follows: : function SCHEDULEX) 2: Y empty list 3 SORTBYSTART(x) // Sort X by start times, ascending order 4: for cin X do if c does not overlap with any class in Y then append c to Y 7: return Y