Find Jobs involved in Weighted Job Scheduling - GeeksforGeeks

Find Jobs involved in Weighted Job Scheduling - GeeksforGeeks

Given N jobs where every job is represented by following three elements of it.

1. Start Time
2. Finish Time
3. Profit or Value Associated

Find the subset of jobs associated with maximum profit such that no two jobs in the subset overlap.

Examples:

Input:    Number of Jobs n = 4  Job Details {Start Time, Finish Time, Profit}  Job 1:  {1, 2, 50}   Job 2:  {3, 5, 20}  Job 3:  {6, 19, 100}  Job 4:  {2, 100, 200}    Output:   Jobs involved in maximum profit are  Job 1:  {1, 2, 50}  Job 4:  {2, 100, 200}  

We strongly recommend you to minimize your browser and try this yourself first.

In previous post, we have discussed about Weighted Job Scheduling problem. However, the post only covered code related to finding maximum profit. In this post, we will also print the jobs invloved in maximum profit.

Let arr[0..n-1] be the input array of Jobs. We define an array DP[] such that DP[i] stores Jobs involved to achieve maximum profit of array arr[0..i]. i.e. DP[i] stores solution to subproblem arr[0..i]. The rest of algorithm remains same as discussed in previous post.

Read full article from Find Jobs involved in Weighted Job Scheduling - GeeksforGeeks