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.
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.
Let's find the nearest compatible job for job X, which starts at time X.
After scanning the list, we see that Therefore, c[X] = . Let's fill in c[X].
Perfect, let's continue.
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.
We need to know the optimal weight from time 0 through job X. First, let's check the M array to see if it has already been computed.
Excellent, this is the last finishing job, so we are finished. The optimal weight we can achieve from our time graph is X.
The entry is blank, so we need to compute the optimal weight ourselves using this equation.
We have computed both possibilities. Now we can compute the maximum.
The greater result was X. Thus, the optimal weight from the beginning through job X is X. Let's assign it to M[X] and fill in the entry in the M array.
This first expression assumes that job X IS part of the optimal chain of jobs. It adds this job's weight X and then computes from the best compatible job.
Let's summarize: If job X is part of the optimal solution, then the maximum weight from the beginning through job X is X.
We need to find the optimal substructure starting from this job's compatible job. Let's look at the c array to get the job number.
The compatible job was job X.
Thus we will compute the total weight from the optimal substructure from time 0 through job X. Let's do that now.
The optimal weight from the beginning through job X was X. Let's add this to job X's weight X.
This second expression assumes that job X is NOT part of the optimal sequence. It computes from the job right behind this one since it doesn't need to worry about overlap.
Let's summarize: If job X is NOT part of the optimal solution, then the maximum weight from the beginning through job X is X.
X-1 is X. So we need to compute the weight from the optimal substructure starting at job X. Let's do that now.
We need to know the optimal weight ending through job X. First, let's check the M array to see if it has already been computed.
The entry already exists. Of course, this is the base case for j = 0. 0 jobs means 0 weight. Let's pass this back up the tree.