We consider an extended version of the activity selection problem discussed during the lecture in week 3. We have a set of lectures {a_1, a_2, ..., a_n} and more than n lecture halls. Each lecture has a start and finish time and we cannot schedule lectures that overlap in the same lecture hall. We want to schedule all the lectures using as few lecture halls as possible. A set X of lectures is compatible in S if X Subsetequalto S and no two lectures in X overlap. As a starting point, the lecturer of COMP333 proposes the following recursive solution: range over the set of compatible subsets of lectures and for each such set compute an optimal for the remaining set of lectures. Formally: OptSchedule(S) = min_X compatible in S (1 + OptSchedule(S \ X)) We want to prove optimal sub-structure for this solution. Prove that an optimal solution for S includes optimal solutions for X (a compatible set of lectures)