Problem 1 We have shown that the algorithm below is not a correct algorithm for Interval Partitioning problem. In the class, we gave a correct algorithm by changing the order of lectures (lne 1 of Algorithm 1) Here we want a different correct algorithm for the same problem by modifying the algorithm below. You are only allowed to change line 5, i.e. you need to decide which classroom to schedule lecture j when there are multiple compatible choices. Justify the correctness of your algorithm For simplicity, you can assume no two jobs have same finish time (Hint: Think about the counterexample in the class.) Algorithm 1 Interval partitioning 1: Sort lectures by finish time so that fi fz-...-In 2: t 0. 3: for j 1 to n do 4: if j is compatible with some existing classroom then 5: et 1