Problem Statement

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 (>= 0)

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.

Reference Video

https://www.youtube.com/watch?v=AxQjrWiOdkE

Code

#include<bits/stdc++.h>
using namespace std;
struct Job
{
    int start;
    int end;
    int profit;
};
static bool compare(Job a,Job b)
{
    return (a.end<b.end);
}
int weightedJobScheduling(Job jobs[],int n) 
{
    vector<int> dp(n);
    for(int i=0;i<n;i++)
        dp[i] = jobs[i].profit;
    sort(jobs,jobs+n,compare); //sorting in ascending order of end time         
// (can also sort wrt to start time)
    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(jobs[i].start>=jobs[j].end and dp[i]<jobs[i].profit+dp[j])
                dp[i] = jobs[i].profit + dp[j];
        }
    }    
   
     return *max_element(dp.begin(),dp.end());   
}
int main() {
    int n;
    cin>>n; // number of jobs
    Job jobs[n];
    for(int i=0;i<n;i++)
    {
        cin>>jobs[i].start>>jobs[i].end>>jobs[i].profit;
    }
    cout<<weightedJobScheduling(jobs,n);
    return 0;
}
// Time Complexity : O(n^2) 
// Space Complexity : O(n)