Consider the weighted interval scheduling problem, we have the following iterative solution (see 1.2.6 (and earlier sections if needed) of

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.

Leave a Reply

Your email address will not be published. Required fields are marked *