Weighted Interval Scheduling (with Dynamic Programming and Memoization)

Maximum Jobs:

Maximum Time:

Maximum Weight:

These blue bars represent jobs A—. You can hover over them to view their stats if you wish (the bottom stats will be explained soon).
Let's place them on the time graph from top to bottom.

Done. We just placed them on the graph in the order you initially defined the jobs, right?

Let's take them back off for a moment. The first step in the process is to sort them in order of finish time, so let's visualize that.
(The sorting method is irrelevant; let's assume that it uses Merge Sort)

Perfect, this will make it easier to visually understand which jobs are compatible with each other.
We can refer to each job by their sorted index. job 0 will be reserved as a non-existent job.

Excellent, we've found every job's nearest compatible job. Our next step is to figure out the optimal (maximum) weight we can obtain from these jobs without having any of them overlap.

The naive or brute force approach would be to test every single combination of jobs, which could be done using this recursive algorithm
OPT(j) {
 if (j = 0)
  return 0;
 else
  return max(wj + OPT(c[j]), OPT(j-1));
}

(where w is weight) and calling OPT(X).

This first term represents the possibility that the current job j is indeed part of the optimal sequence of jobs. Thus, it adds job j's weight, and then it adds whatever the optimal weight is from the chain starting at job c[j].
Why? Because if job j is part of the optimal chain, then the latest preceding job that could possibly also be in the chain is one that doesn't overlap, i.e. job j's nearest compatible job.

This second term represents the possibility that job j is NOT part of the optimal sequence of jobs. Thus, of course, job j's weight is NOT added, and it then computes the optimal weight starting from the job behind it, job j - 1.

The problem with the naive approach is that it may recompute many overlapping subproblems. In other words, we might solve the same OPT(X) multiple times, which is incredibly inefficient.

Time
j

Next, we will find each job's nearest "compatible" job. For a job Jx, another job Jy is compatible with Jx if Jy.finish ≤ Jx.start. That is to say, Jy ends before or as soon as Jx begins.
Thus, Jx's NEAREST compatible job will be Jy such that y is maximized.

This green c array to the left will be used to store the index of each job's compatible job. If a job does not have a compatible job, we will give its c array entry the value 0.
Now, let's begin.

Perfect, let's continue.

c[j]
j

The solution is actually simple: Every time we find the optimal weight for a sequence from time 0 to some job, let's store it in an array. Then, every time we call OPT(j) for some job j, we first check if it has already been solved by looking in the array.
This act of storing results in a table to prevent needless recalculations is called memoization.

This purple M array to the left will be used as our memoization table; it will store the result of each job's OPT() computation. If we have 0 jobs, of course the optimal weight would be 0, so our base case is that M[0] = 0.

Our new memoized weighted interval scheduling algorithm looks like this:
OPT(j) {
 if (M[j] = empty)
  M[j] := max(wj + OPT(c[j]), OPT(j-1));
 return M[j]
}

Let's go ahead and call OPT(X) and find the maximum weight we can achieve from jobs A—X.

M[j]