Job Sequencing Problem

December 30, 2021

Job Sequencing Problem

In the Job Sequencing Problem we are given a list of jobs/activities with their associated profits. We have to determine maximum amount we can earn. The problem can be solved optimally using greedy algorithm. In this article we will provide a C++ solution with an explanation.

Job Sequencing Problem Description

Given a list of jobs/activities. Each job is associated with a deadline and a profit (amount that can be earned). The job cannot be performed after it’s deadline. Assuming each job takes one unit of time and at a time only one job can be performed. Determine the maximum profit possible.

Input:

First line contains single integer n – the number of jobs .
Next n lines contains two integers – the deadline and profit of ith activity.

Output:

The maximum profit possible.

Job Sequencing Problem Solution

The problem can be solved using greedy algorithm. Since we have to find the maximum profit we will always pick job with maximum profit first and will try to finish it as close to its deadline as possible..

Why? Because placing such a job nearer to it’s deadline will enable to to complete more test with lesser profit value.

Steps–

Sort the job in decreasing order of their profit.
Iterate on all jobs.
For ith job iterate on all possible time slots from it’s deadline to 1 & place the job on first empty time slot.

Time Complexity – O(n^2)

Space Complexity – O(n)

Code

#include <bits/stdc++.h>
using namespace std;
class job
{
public:
    int deadLine, profit;
};
bool compare(job A, job B)
{
    return A.profit > B.profit;
}
int main()
{
    int n;
    cin >> n;

    job arr[n];

    for (int i = 0; i < n; i++)
        cin >> arr[i].deadLine>> arr[i].profit;

    sort(arr, arr + n, compare);

    int profit[n], totalProfit = 0;

    for (int i = 0; i < n; i++)
        profit[i] = –1;

    for (int i = 0; i < n; i++)
    {
        int deadLine = arr[i].deadLine;

        for (int j = deadLine; j >= 1; j–)
        {
            if (profit[j] == –1)
            {
                profit[j] = arr[i].profit;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (profit[i] > –1)
            totalProfit += profit[i];
    }

    cout << “Total Profit = “ << totalProfit << endl;

    return 0;
}

Output

5
3 100
2 20
1 50 
3 40
2 40
Total Profit = 190