Consider the weighted interval scheduling problem, we have the following iterative solution (see 1.2.6 (and earlier sections if needed) of L6) to the problem: Assume we have n requests (1. n). For each request i, v) is the value of I. Recall we have defined function previous in class. Line 1: for i from 0 ton, M[:= 0. Line 2: for i from 1 ton, MD := max(vl) + M [previous), M[i-1])
a) Write down precisely what is the intended meaning of the data structure MI.]
b) Why do we do line 1?
c) Explain the meaning of MCU := max(v+ M[previous), M[i-1]) in Line 2.