Problem 2: Course room assignment You have n lectures that need to be allocated rooms. Each lecture has its own 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: Sort lectures in some way (to be determined) d 0 number of allocated classrooms for j = 1 to n { if (lecture j is compatible with some classroom k) schedule lecture j in clas s rom k else allocate a new classroom d 1 schedule lecture j in classroom d1 d: d 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 work here. (b) Prove that sorting by start time always gives the optimal solution (c) Show that your algorithm is O (n log n). Problem 2: Course room assignment You have n lectures that need to be allocated rooms. Each lecture has its own 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: Sort lectures in some way (to be determined) d 0 number of allocated classrooms for j = 1 to n { if (lecture j is compatible with some classroom k) schedule lecture j in clas s rom k else allocate a new classroom d 1 schedule lecture j in classroom d1 d: d 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 work here. (b) Prove that sorting by start time always gives the optimal solution (c) Show that your algorithm is O (n log n)