title: Dynamic Programming Recurrence to Solution
body: <p>I'm trying to solve the weighted interval scheduling problem. Basically, I came up with the following recurrence to obtain the length of the optimum solution:</p>
  
  <pre><code>optimum[i] = max(duration(intervals[i]) + opt[prior[i]], opt[i - 1])
  </code></pre>
  
  <p>where prior[i] = the latest non-overlapping schedule that finishes before current interval starts.</p>
  
  <p>The recurrence works well and I get the correct solution. However, I want to get the actual schedule and not just the length. How can I do that? I tried by starting from the largest p[i] value and following the pointer until I reach None / -1 / Null but that doesn't always work. I assume I need to keep track of which intervals to keep and which to discard as I solve the recurrence above. I tried by doing something like:</p>
  
  <pre><code>if (duration(intervals[i]) + optimum[prior[i]] &gt;= optimum[i - 1]) {
    optimum[i] = duration(intervals[i]) + optimum[p[i]];
    retain[i] = true;
  }
  else {
    optimum[i] = optimum[i - 1];
    retain[i] = false;
    retain[i - 1] = true;
  }
  </code></pre>
  
  <p>But this didn't work well.</p>