Dynamic Programming Solution Repeat

Question

I am trying to solve the problem of planning weighted intervals. Basically, I got the following repetition to get the length of the optimal solution:

optimum[i] = max(duration(intervals[i]) + opt[prior[i]], opt[i - 1])

where previously [i] = the last non-overlapping schedule ending before the start of the current interval.

Repetition works well and I get the right solution. However, I want to get the actual schedule, not just the length. How can i do this? I tried to start with the largest p [i] and after the pointer, until it reaches None / -1 / Null, but this does not always work. I assume that I need to keep track of which intervals to keep and discard when I decide the repetition above. I tried to do something like:

if (duration(intervals[i]) + optimum[prior[i]] >= 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;
}

But that did not work.

Answer 1

prior[i], optimum[i] . , i . .

queue<int> path;
int st = i;
while (st > 0) {
  if (op[st] == op[st-1]) st = st -1;
  else {
    path.push(st);
    st = prior[st];
  }
}
pop each item from queue<int> path, you get the intervals you selected.