Scribd
Upload
47 views7 pages

Interval Scheduling

The document outlines a method for selecting a subset of jobs with maximum total profit while ensuring no overlapping jobs occur. It introduces a recursive approach using a function OPT(j) to calculate the maximum weight achievable by selecting jobs from the first j intervals, considering both cases of including or excluding the last job. The time complexity for the algorithm is O(n log n) for sorting and finding overlaps, with O(n) for calculating the maximum weight and backtracking to identify selected jobs.

Uploaded by

rsinglame24
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
47 views7 pages

Interval Scheduling

The document outlines a method for selecting a subset of jobs with maximum total profit while ensuring no overlapping jobs occur. It introduces a recursive approach using a function OPT(j) to calculate the maximum weight achievable by selecting jobs from the first j intervals, considering both cases of including or excluding the last job. The time complexity for the algorithm is O(n log n) for sorting and finding overlaps, with O(n) for calculating the maximum weight and backtracking to identify selected jobs.

Uploaded by

rsinglame24
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Given a list of jobs which has a start, finish time and a

profit/weight associated with it: we want to find the subset


with the maximum total weight where each job is disjoint (The
jobs cannot occur at the same time).
Idea: If we assume we only look at the last job when having sorted the jobs by finish time,
then either we pick it or we don't.

Case 1 (We pick it): Then we need to remove all overlapping jobs and compute the solution
for the subproblem of the jobs left.

Case 2 (We don't pick it): Then we simply compute optimal solution for the subproblem with
n - 1 items left.

We can do this recursively for j = 1, 2, ..., n and we define OPT(j) = "Maximum weight that can
be achieved by selecting the jobs from first j intervals"
Let's define a help function: let p(j) be the largest index i such that f_{i} ≤ s_{j}.
This function is useful to remove overlapping jobs. Let us understand this function
with an example.
Let us combine the two cases into a recursion formula, and we want to pick whichever is best:

OPT(j) = max{w_{j} + OPT(p(j)), OPT(j-1)}

With base case: OPT(0) = 0

Now let's gain some more intuition by seeing how we use this algorithm on the same example.
Note: all jobs are sorted by finish times.

OPT(j) = max{w_{j} + OPT(p(j)), OPT(j-1)}

j 1 2 3 4 5 6 7 8
w_{j} 3 2 4 1 2 5 2 1
p_{j}
OPT(j)
j 1 2 3 4 5 6 7 8
wj 3 2 4 1 2 5 2 1
P(j) 0 0 0 1 2 1 3 5
OPT(j) 3 3 4 4 5 8 8 8
What we then want to return is OPT(n) which is the maximum weight for all items.

The solution for finding which items we picked is by backtracking, simply if


w_{j} + OPT(p(j)) ≥ OPT(j-1) then we add item j to optimal solution and look at OPT(p(j))
else we ignore this item and look at subproblem OPT(j-1).

Time complexity:
Sorting is O(nlogn)

Finding p(j), j=1,2,..,n has time complexity O(nlogn) (clever use of binary search)
To find find maximal weight (when p found): O(n)

Backtrack to find optimal items: O(n)

You might also like