Design an algorithm such that maximum number of jobs can be performed in that given time interval.

You are given N jobs with their start and end time mentioned.These jobs may have their timings overlapped.You have to suggest an algorithm such that maximum number of jobs can be performed in that given time interval.

Given a set of n jobs j1, j2, · · · , jn, find a set of compatible jobs with the

maximum weight.
• Each job ji starts at sji and and finishes at fji .
• Each job ji has weight (value) vji .
• Two jobs are compatible if their intervals do not overlap.
In other words, we are trying to find a set of jobs ji1 , ji2 , · · · , jik such that the following is maximized:

sum(vjix) for each x=1 to k

The dynamic programming paradigm gives us two options when examining
each job. The optimal solution either contains the job, or it doesn’t. As
an example, if the optimal solution contains j1, then we pick j1 and find the
optimal solution for jobs compatible with j1. If the optimal solution does
not contain j1, then we find the optimal solution for j2, j3, · · · , jn. (This assumes that the jobs are arranged in order of their finish time, such that fj1
Once we select a job to be a part of the optimal solution, we exclude a
host of other jobs that are incompatible with the selection. To assist in our
definition of an optimal solution, we define jip to be the largest index job,
ip < i, that is compatible with ji. In other words, jip is the job for which
sji − fjip is minimized.

We can then let OPT(i) be the set containing the optimal solution for
jobs j1, j2, · · · , ji. It is defined as follows for each ji:

• Case 1: OPT selects ji
– We cannot select jobs jip+1, · · · , ji−1, so we exclude them from
consideration.
– We recurse and find the optimal solution for jobs j1, j2, · · · , jip by
setting OPT(i) = vji + OPT(ip).

• Case 2: OPT does not select ji
– We recurse and find the optimal solution for jobs j1, j2, · · · , ji−1
by setting OPT(i) = OPT(i − 1).

Since we don’t know which case will return the optimal solution, we must
try both. Once we have calculated both possibilities, we pick the case which
returns the larger set. Now we can create a more compact definition, together
with a simple implementation:

OPT(i) = max{vji + OPT(ip),OPT(i − 1)} | i 1
= 0 | otherwise

The recursive algorithm looks like

COMPUTE_OPT(i):
if i == 0:
return 0
return max {
COMPUTE_OPT(i - 1),
v[j(i)] + COMPUTE_OPT(p(i))
}

The problem with the algorithm as it stands is that a lot of computation is
repeated. This is visualized by looking at the recursive tree structure:

-COMPUTE_OPT(5)
-COMPUTE_OPT(3)
-COMPUTE_OPT(1)
-COMPUTE_OPT(2)
-COMPUTE_OPT(0)
-COMPUTE_OPT(1)
-COMPUTE_OPT(4)
-COMPUTE_OPT(2)
-COMPUTE_OPT(0)
-COMPUTE_OPT(1)
-COMPUTE_OPT(3)
-COMPUTE_OPT(1)
-COMPUTE_OPT(2)
-COMPUTE_OPT(0)
-COMPUTE_OPT(1)

It is easy to see that for even a small set of jobs, the amount of repeated
computation is huge. To avoid this, we introduce memoization, which stores
the values for OPT(i) in a global array as they are calculated. If the value is
needed later, it is simply retrieved from the array, pruning the recursive tree
such that each descent only happens once. The following revised algorithm
implements memoization:
M_COMPUTE_OPT(i):
if M[i] != null:
return M[i]
if i == 0:
M[0] = 0
else:
M[i] = max {
M_COMPUTE_OPT(i - 1),
v[j(i)] + M_COMPUTE_OPT(p(i))
}
return M[i]

This memoized version saves valuable computational resources, but each
recursive call adds overhead. The algorithm runs in O(n) time, but its recursive
nature makes it bulky.

We can eliminate the overhead of recursion by constructing an iterative (nonrecursive)
algorithm that builds a bottom-up list of the values.
M[0] = 0
for i = 1 to n:
M[i] = max {
M(i - 1),
v[j(i)] + M(p(i))
}
This is obviously linear, and without the added computational weight of
a recursive algorithm. To reconstruct the solution, we simply run backwards
through the array (take M[n] and compare to M[n-1], etc.).
PRINT_SOLUTION(i):
if i == 0:
return
if v[j(i)] + M[p(i)] == M[i]:
print j(i)
PRINT_SOLUTION(p(i))
else:
PRINT_SOLUTION(i - 1)

Time Complexity O(N)
Space Compleixty O(N)


Resources
http://en.wikipedia.org/wiki/Interval_scheduling
http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec3.pdf
http://www.cs.cornell.edu/courses/cs482/2007sp/dynamic.pdf
http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf
http://www.cs.sfu.ca/~ssa121/personal/spring08/705/dp.pdf
http://www.cs.uiowa.edu/~hzhang/c31/6-dynamic.pdf
classes.soe.ucsc.edu/.../06dynamic-programming-weighted-interv-sched.ppt
http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/06dynamic-programming.pdf
http://www.cse.psu.edu/~asmith/courses/cse565/F08/www/lec-notes/CSE565-F08-Lec-17.pdf