30

Question 2: (35 Marks) Suppose you have a set of n lectures that need to be scheduled in classrooms. Each lecture has fixed starting and ending times. You would like to use as few classrooms as possible to schedule all lectures. For example: Lectures Starts: Ends: 1 9:00 10:30 2 3 4 5 9:00 9:00 11:00 11:00 12:30 10:30 12:30 2:00 6 1:00 2:30 7 1:00 2:30 8 2:00 4:30 9 3:00 4:30 10 3:00 4:30 These lectures can be scheduled in 3 classrooms. a) Explain how a brute force algorithm would solve this problem and analyze its complexity. (3+2 marks) b) Design a more efficient algorithm to solve this problem (8 marks), and analyze its complexity (4 marks) [Important instruction: Create an arbitrary list of 10 lectures starting