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$ to the weight of job $ 3$ but $ M$ 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$ ?