Home » Interview coding problems/challenges

Weighted Job Scheduling

Maximum Profit in Job Scheduling: Here, we are going to learn the solution of weighted job scheduling using recursion and dynamic approach.
Submitted by Divyansh Jaipuriyar, on August 17, 2020

Problem statement:

You are given a list of jobs where each job has a start time, finish time, and the profit associated with that job, find the maximum profit subset of non-overlapping jobs.

Problem description:

The problem wants you to find the maximum profit that you can make after performing a certain number of jobs such that each job has a certain condition that you can start a job only if the start time of the current job is greater than the finish time of the previous job. You are required to develop some algorithm such that the job start time and the finish time does not coincide with other jobs.

Input:

The first line of the input consists of T number of test cases, each test case consists of N number of jobs, each for the following N lines consists of the start time, finish time and the profit for that job.

Output:

Print the maximum value of the profit that you can get after performing the given jobs in a separate lines.

Examples:

Input:
T=1
N=3
0 6 60
5 7 30
7 8 10

Output:
70, 
as 0->6 and then 7->8 which in total gives 60 + 10 =70.

Input:
T=1
N=3
1 2 30
2 3 40
4 8 60

Output:
130,
as 1->2,2->3 and then 4->8 which in total gives (30+40+60).

Solution approach:

1) Recursive Approach:

In this approach we will use recursion, we will create a structure of job which will have three variable st, en and pr which will have st is equal to start, en is the end and pr will be profit.

1. First, we will store the entire jobs in a vector.
2. Then we sort the vector in increasing order to their finish time.
3. Then we finally make a recursive call to the solve function which will take inputs as the vector of job and the index from where we are starting.

There are two possibilities for each job, either that job is included in the overall profit or otherwise, it is not included.

If that job is included in overall profit-making then we have to recur for those jobs which do not make any conflict with the selected job, so we make a find function which will take vector and index as a parameter and return the index of non-conflict job.

In order to find the index of the job index which do not make any intersection with the current selected job, we can also use a binary search method to reduce the time complexity.

The second possibility with the current job is that the selected job is not included in the overall profit.

Time Complexity for the above approach in the worst case is exponential

Space complexity for the above approach is O(n)

2) Dynamic Programming Approach:

In this approach we will use memoization technique, we will create a dp[] state, each time we make a recursive call

we store that result in the dp[] state, we will initialize all dp[] state with -1, if the dp[] is -1 then it means that has not been calculated so we need to calculate it and if it is not -1 then we will directly return it.

Time Complexity for the above approach in the worst case is: O(n*n)

Space complexity for the above approach in the worst case is: O(n)

C++ Implementation (Recursive Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//user defined job data type.
struct job { //start,end and profit.
    ll st, en, pr;
};

//fun function for checking
//smallest of two job on basis
//of their finish time.
bool fun(const job& j1, const job& j2)
{
    if (j1.en < j2.en)
        return true;
    else
        return false;
}

//find1 function using binary search
//it reduces the time complexity
ll find1(vector<job>& v1, ll n)
{
    //start variable for binary search.
    ll st = 0;
    //end variable for binary search.
    ll en = n;
    //search under range of binary
    //search boundary.
    while (st <= en) {
        //find mid index.
        ll mid = st + (en - st) / 2;
        //if mid index element has finish time less
        //than equal to start time of nth index element.
        if (v1[mid].en <= v1[n].st) {
            if (v1[mid].en <= v1[n].st) {
                //check for nrearest index to current
                //nth element.
                if (v1[mid + 1].en <= v1[n].st)
                    st = mid + 1;
                else
                    return mid;
            }
        }
        else //reduce search spaces.
            en = mid - 1;
    }
    //if no other non intersecting job is found.
    return -1;
}

//find function working in linear time.
ll find(vector<job>& v1, ll n)
{
    //iterate through all elements
    //and check which job is non intersecting.
    for (ll i = n - 1; i >= 0; i--) {
        if (v1[i].en <= v1[n].st)
            return i;
    }
    //if not found then return -1.
    return -1;
}

//solve function which will return maximum
//profit.
ll solve(vector<job>& v1, ll n)
{
    //if one job is remaining.
    if (n == 0)
        return v1[n].pr;

    //if index if out of bound.
    if (n < 0)
        return 0;

    //find index of nearest job which is
    //non intersecting to curent job.
    ll id = find1(v1, n);

    //find profit by including current
    //index profit.
    ll p1 = v1[n].pr + solve(v1, id);

    //find profit by not including
    //current index element.
    ll p2 = solve(v1, n - 1);

    //return maximum value.
    return max(p1, p2);
}

int main()
{
    ll t, st, en, pr;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter number of jobs: ";
        ll n;
        cin >> n;

        vector<job> v1;

        cout << "Enter job details:\n";
        for (ll i = 0; i < n; i++) {
            cin >> st >> en >> pr;
            v1.push_back({ st, en, pr });
        }

        //sort according to finish time.
        sort(v1.begin(), v1.end(), fun);
        cout << "Maximum profit: ";
        cout << solve(v1, n - 1) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 2
Enter number of jobs: 3
Enter job details:
0 6 60
5 7 30
7 8 10
Maximum profit: 70
Enter number of jobs: 6
Enter job details:
1 4 30
3 5 10
5 7 30
0 6 60
7 8 10
5 9 50
Maximum profit: 80

C++ Implementation (Dynamic Programming Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//declare dp state.
ll dp[100005];

//user defined job data type.
struct job { //start,end and profit.
    ll st, en, pr;
};

//fun function for checking
//smallest of two job on basis
//of their finish time.
bool fun(const job& j1, const job& j2)
{
    if (j1.en < j2.en)
        return true;
    else
        return false;
}

//find1 function using binary search
//it reduces the time complexity
ll find1(vector<job>& v1, ll n)
{
    //start variable for binary search.
    ll st = 0;
    //end variable for binary search.
    ll en = n;
    //search under range of binary
    //search boundary.
    while (st <= en) {
        //find mid index.
        ll mid = st + (en - st) / 2;
        //if mid index element has finish time less
        //than equal to start time of nth index element.
        if (v1[mid].en <= v1[n].st) {
            if (v1[mid].en <= v1[n].st) {
                //check for nearest index to current
                //nth element.
                if (v1[mid + 1].en <= v1[n].st)
                    st = mid + 1;
                else
                    return mid;
            }
        }
        else //reduce search spaces.
            en = mid - 1;
    }
    //if no other non intersecting job is found.
    return -1;
}

//find function working in linear time.
ll find(vector<job>& v1, ll n)
{
    //iterate through all elements
    //and check which job is non intersecting.
    for (ll i = n - 1; i >= 0; i--) {
        if (v1[i].en <= v1[n].st)
            return i;
    }
    //if not found then return -1.
    return -1;
}

//solve function which will return maximum
//profit.
ll solve(vector<job>& v1, ll n)
{
    //if one job is remaining.
    if (n == 0)
        return v1[n].pr;

    //if index if out of bound.
    if (n < 0)
        return 0;

    //check if already calculated.
    if (dp[n] != -1)
        return dp[n];
    //find index of nearest job which is
    //non intersecting to current job.
    ll id = find1(v1, n);

    //find profit by including current
    //index profit.
    ll p1 = v1[n].pr + solve(v1, id);

    //find profit by not including
    //current index element.
    ll p2 = solve(v1, n - 1);

    //return maximum value.
    return dp[n] = max(p1, p2);
}

int main()
{
    ll t, st, en, pr;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter number of jobs: ";
        ll n;
        cin >> n;

        vector<job> v1;

        //initialize dp state with -1.
        memset(dp, -1, sizeof(dp));
        cout << "Enter job details:\n";
        for (ll i = 0; i < n; i++) {
            cin >> st >> en >> pr;
            v1.push_back({ st, en, pr });
        }

        //sort according to finish time.
        sort(v1.begin(), v1.end(), fun);
        cout << "Maximum profit: ";
        cout << solve(v1, n - 1) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter number of jobs: 3
Enter job details:
1 4 30
5 7 30
1 3 40
Maximum profit: 70
Enter number of jobs: 2
Enter job details:
1 7 120
3 6 230
Maximum profit: 230
Enter number of jobs: 3
Enter job details:
1 2 30
2 3 40
4 8 60
Maximum profit: 130