10.1 Weighted Interval Scheduling

Question 1

What is weighted interval scheduling?

Answer 1

• Interval scheduling but with a weight function
• Maximise total weight (intstead of interval count)
• Means greedy algorithm is no longer effective

Question 2

What are the 3 steps of dynamic programming?

Answer 2

• Step 1: Exponential recursive solution (find optimal substructure - often based on YES NO choices - 2 cases)
• Step 2: Make it such that there is repeated work (which can be stored)
• Step 3 (optional): Make it itterative using table

Question 3

What is the idea behind constructing a recursive version of interval scheduling?

Answer 3

• For interval I, it is either in the set or not, so recurse on both cases

Question 4

What is the recursive psuedocode for weighted interval scheduling?

Answer 4