Weighted Job Scheduling

Geeks

Description:

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

Start Time Finish Time Profit or Value Associated

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

Example:

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: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3 
but the profit with this schedule is 20+50+100 which is less than 250.

Idea:

Similar to Knapsack problem. Tricky to deal with non-conflicting.

1) First sort jobs according to finish time.
2) Now apply following recursive process. 
   // Here arr[] is array of n jobs
   findMaximumProfit(arr[], n)
   {
     a) if (n == 1) return arr[0];
     b) Return the maximum of following two profits.
         (i) Maximum profit by excluding current job, i.e., 
             findMaximumProfit(arr, n-1)
         (ii) Maximum profit by including the current job            
   }

How to find the profit including current job?
The idea is to find the latest job before the current job (in 
sorted array) that doesn't conflict with current job 'arr[n-1]'. 
Once we find such a job, we recur for all jobs till that job and
add profit of current job to result.
In the above example, "job 1" is the latest non-conflicting
for "job 4" and "job 2" is the latest non-conflicting for "job 3".

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Job{
    int start;
    int finish;
    int profit;
    Job(int i, int j, int k): start(i), finish(j), profit(k) {}

    bool operator < (const Job& rhs) const{
        return finish<rhs.finish;
    }
};

int latestNonconflict(int i, const vector<Job>& jobs){
    for(int j=i-1; j>=0; j--){
        if(jobs[j].finish<=jobs[i-1].start){
            return j;
        }
    }
    return -1;
}

int findMaxProfitHelper(int n, const vector<Job>& jobs, vector<int>& memo){
    if(memo[n] != -1)
        return memo[n];
    if(n==1){
        memo[1] = jobs[0].profit;
        return memo[1];
    }
    int maxProfit = INT_MIN;
    int i=latestNonconflict(n, jobs);
    if(i!=-1){
        maxProfit=max(maxProfit, jobs[n-1].profit + findMaxProfitHelper(i+1, jobs, memo));
    }
    maxProfit = max(maxProfit, findMaxProfitHelper(n-1, jobs, memo));
    memo[n] = maxProfit;
    return maxProfit;
}

int findMaxProfit(vector<Job> jobs){
    sort(jobs.begin(), jobs.end());
    vector<int> memo(jobs.size()+1, -1);
    return findMaxProfitHelper(jobs.size(), jobs, memo);
}

int main(){
    vector<Job> jobs;
    jobs.push_back({3, 10, 20});
    jobs.push_back({1, 2, 50});
    jobs.push_back({6, 19, 100});
    jobs.push_back({2, 100, 200});

    // int i = jobs[0]<jobs[1];

    cout<<findMaxProfit(jobs);
}