Suppose you have n lectures that need to be allocated to available classrooms. Each lecture i has a start time si and finish time fi. Your goal is to assign lectures to rooms using as few rooms as possible. Of course, if two lectures overlap in time, they cannot share a room. (a) Consider the following greedy algorithm skeleton: 1 Sort lectures in some way (tbd) 2d0 3 for j1 to n do if lecture j is compatible with some classroom k then schedule lecture j in classroom k else allocate a new classroom d+1 schedule lecture j in classroom d+1 dd+1 You remember that you learned about interval scheduling in class, and for that problem you needed to sort by finish times. Show by counter-example that sorting by finish times doesn't always work here. (b) Prove that sorting by start time always gives the optimal solution. (c) Show that your algorithm is O(nlogn)