# Weighted interval scheduling: index out of range

Let's say these jobs are given:

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$$?

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