6.1 Weighted Interval Scheduling

Question 1

What is the weighted interval scheduling problem?

Answer 1

The goal is to maximize the reward by selecting non-overlapping intervals.

Question 2

What is the function P(i) in the interval scheduling solution where “i” is the index of an interval?

Answer 2

It returns the highest index of the previous intervals that interval “i” does not overlap with.

Question 3

What is the OPT function in the weighted interval scheduling problem? Use function P.

Answer 3

OPT(j) = max((w_j + OPT(P(j))), (OPT(j-1)))

Question 4

What is the problem with implementing the solution to WIS in it simplest form.

Answer 4

As each interval results in two function calls, the algorithm would take o(2^n) in time, exponential.

Question 5

How can the problem that a WIS solution is in exponential time be solved?

Answer 5

By memorizing the results of function calls to the opt function: Storing the result the first time we compute them.

Question 6

What is the time complexity of the memorization solution to WIS?

Answer 6

O(n):
As the memory has n+1 slots and we fill this array, there can be at most O(n) calls to Compute-Opt. SInce compute opt is constant O(1), we get O(n).

Question 7

How can you get the solution in addition to its value?

Answer 7

By at each memory slot use a pointer that indicates what value was used in the calculation of this value:
Backtracing.