Let's say these jobs are given:

Interval scheduling

where $p$ determines the last not overlapping job. Now I create a Memorization Array $M$ and calculate for every index $j$: $\omega_j + M[p(j)]$ and $M[j-1]$ where $\omega_j$ stands for the weight. So I started with job $2$ since that one is the first job to start. That gives me $\omega_j + M[p(j)] = 3 + 0$ and $M[j-1] = 0$ since the first entry of my array is always $0$. In the same way, I calculate $\omega_j + M[p(j)]$ and $M[j-1]$ for job $5$ (because $5$ starts after $2$).

Now job $3$ is the next to start and that's where I get confused. $p(3)$ should be $5$ since job $5$ ends at $14$. So that means that I have to add $M[5]$ to the weight of job $3$ but $M[5]$ is not initialized yet.

So my question is, what is the correct way to work around this? Does the algorithm take Job $2$ instead of $5$ for $p(3)$? Or does it take job $5$ and initialize $\omega_5 + M[p(5)]$ as soon as $M$ has a value for index $5$?

  • $\begingroup$ It seems like you have a bug. Try to understand the algorithm, then you’ll be able to program it correctly. $\endgroup$ – Yuval Filmus May 30 '19 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.