Weighted Interval Scheduling Problem

Given a list of jobs where each job has a start and finish time, and also has profit associated with it, find maximum profit subset of non-overlapping jobs.


 

For example, consider below jobs with their starting time, finishing time, and associated profit.

 

Job 1: (0, 6, 60)
Job 2: (1, 4, 30)
Job 3: (3, 5, 10)
Job 4: (5, 7, 30)
Job 5: (5, 9, 50)
Job 6: (7, 8, 10)

 
The maximum profit is 80 which is achieved by picking job 2 and Job 5.

 
This problem is standard variation of Activity Selection Problem. The greedy algorithm works fine for Activity Selection Problem since all jobs have equal weight. But greedy approach won’t work with weighted jobs since even single job may have more profit than all jobs combined.

 

1. Naive Recursive Solution

 
The idea is to sort the jobs in increasing order of their finish times and then use recursion to solve this problem. For each job, there are two possibilities –
 

  1. We include current job in result and recur only for non-conflicting jobs with the current job. Since the jobs are sorted according to their finish times, we can find the last non-conflicting job by performing a linear search or binary search on the sorted input.
     
  2. We exclude current job from result and recur for remaining items.

 

Finally, we return maximum profit we get by including or excluding current job. The recursive algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

The maximum profit is 80

 
The time complexity of above solution is exponential and auxiliary space used by the program is O(n) for recursive call stack.

 

2. Dynamic Programming Solution

 
The above solution has an optimal substructure and also exhibits overlapping subproblems. So we can solve this problem in bottom-up manner using Dynamic Programming, in which we solve smaller sub-problems first, then solve larger sub-problems from them. The bottom-up approach can be implemented as follow:

 

Download   Run Code

Output:

The maximum profit is 80

 
The time complexity of above solution is O(n2) where n is the number of items in the input. The auxiliary space used by the program is O(n).

 

3. Optimized Dynamic Programming Solution

 
We can further optimize above dynamic programming solution to run in O(nlog(n)) time by using Binary Search algorithm to find the last non-conflicting job. The algorithm can be implemented as follows in C++:

 

Download   Run Code

 

4. Printing all jobs involved in the maximum profit

 

The idea is similar to above bottom-up approach using Dynamic Programming, but we maintain an extra array to store the index of jobs involved in the maximum profit. This is demonstrated below in C++:

 

Download   Run Code

Output:

The maximum profit is 80
The jobs involved in the maximum profit are: (1, 4, 30) (5, 9, 50)

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of