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

For example, consider the following 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.

Practice this problem

This problem is a standard variation of the Activity Selection Problem. The greedy algorithm works fine for the activity selection problem since all jobs have equal weight. But the greedy approach won’t work with weighted jobs since even a 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. Include the current job results 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. Exclude the current job from the result and recur for the remaining items.

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

## C++

Output:

The maximum profit is 80

## Java

Output:

The maximum profit is 80

## Python

Output:

The maximum profit is 80

The time complexity of the above solution is exponential and occupies space in the call stack.

## 2. Dynamic Programming Solution

The above solution has an optimal substructure and also exhibits overlapping subproblem. So, we can solve this problem in a bottom-up manner using dynamic programming, in which we solve smaller subproblems first, then solve larger subproblems from them. The bottom-up approach can be implemented as follows in C++, Java, and Python:

## C++

Output:

The maximum profit is 80

## Java

Output:

The maximum profit is 80

## Python

Output:

The maximum profit is 80

The time complexity of the above solution is O(n2) and requires O(n) extra space, where `n` is the total number of jobs.

## 3. Optimized Dynamic Programming Solution

We can further optimize the above dynamic programming solution to run in O(n.log(n)) time using the binary search algorithm to find the last non-conflicting job. The algorithm can be implemented as follows in C++, Java, and Python:

## C++

Output:

The maximum profit is 80

## Java

Output:

The maximum profit is 80

## Python

Output:

The maximum profit is 80

## 4. Printing all jobs involved in the maximum profit

The idea is similar to the 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++, Java, and Python:

## Python

Output:

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

Rate this post

Average rating 4.88/5. Vote count: 217

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post? 