Job Sequencing Problem

Problem#

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline.
It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1.
Maximize the total profit if only one job can be scheduled at a time.

Input and Output#

Input Format
- First line contains \(n\) denoting the number of jobs
- Next \(n\) line each contain job-id, deadline and profit of jobs.

Test Case

Case 1Case 2

c a

c a e

Solutions#

Naive Approach#

Generate all subsets of a given set of jobs
and check individual subsets for the feasibility of jobs in that subset.
Keep track of maximum profit among all feasible subsets.

C++

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

using namespace std;

struct Job {
  char id;
  int dead;
  int profit;
};

void printJobScheduling(vector<Job>& arr) {
}

int main() {
  int n;
  cin >> n;
  vector<Job> arr(n, {'a', 0, 0});
  for (int i = 0; i < n; i++) cin >> arr[i].id >> arr[i].dead >> arr[i].profit;
  printJobScheduling(arr);
  return 0;
}

Time Complexity: \(O(2^n)\)
Auxiliary Space: \(O(n)\)
\(n\) - no of jobs

Greedy approach#

Greedily choose the jobs with maximum profit first, by sorting the jobs in decreasing order of their profit. This would help to maximize the total profit as choosing the job with maximum profit for every time slot will eventually maximize the total profit

Follow the given steps to solve the problem:

Sort all jobs in decreasing order of profit.
Iterate on jobs in decreasing order of profit.For each job , do the following :
Find a time slot i, such that slot is empty and i < deadline and i is greatest. Put the job in this slot and mark this slot filled.
If no such i exists, then ignore the job.

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Job {
  char id;
  int dead;
  int profit;
};

void printJobScheduling(vector<Job> arr) {
  int n = arr.size();
  sort(arr.begin(), arr.end(), [](const Job& a, const Job& b) { return a.profit > b.profit; });

  vector<int> result(n);
  vector<bool> slot(n, false);

  for (int i = 0; i < n; i++) {
    for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
      if (slot[j] == false) {
        result[j] = i;
        slot[j] = true;
        break;
      }
    }
  }

  for (int i = 0; i < n; i++)
    if (slot[i])
      cout << arr[result[i]].id << " ";
}

int main() {
  int n;
  cin >> n;
  vector<Job> arr(n, {'a', 0, 0});
  for (int i = 0; i < n; i++) cin >> arr[i].id >> arr[i].dead >> arr[i].profit;
  printJobScheduling(arr);
  return 0;
}

Time Complexity: \(O(n^2)\)
Auxiliary Space: \(O(n)\)
\(n\) - no of jobs

Priority-Queue (Max-Heap)#

Sort the jobs in the increasing order of their deadlines and
then calculate the available slots between every two consecutive deadlines while iterating from the end.
Include the profit of the job at the root of the Max-Heap while the empty slots are available and Heap is not empty, as this would help to choose the jobs with maximum profit for every set of available slots.

Follow the given steps to solve the problem:

Sort the jobs based on their deadlines.
Iterate from the end and calculate the available slots between every two consecutive deadlines.
Insert the profit, deadline, and job ID of ith job in the max heap.
While the slots are available and there are jobs left in the max heap, include the job ID with maximum profit and deadline in the result.
Sort the result array based on their deadlines.

C++

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Job {
  char id;
  int dead;
  int profit;
};

void printJobScheduling(vector<Job> arr) {
  int n = arr.size();
  vector<Job> result;
  sort(arr.begin(), arr.end(), [](Job a, Job b) { return a.dead < b.dead; });
  auto compare = [](const Job& a, const Job& b) { return a.profit < b.profit; };
  priority_queue<Job, vector<Job>, decltype(compare)> pq(compare);

  for (int i = n - 1; i >= 0; i--) {
    int slot_available = (i == 0) ? arr[i].dead : (arr[i].dead - arr[i - 1].dead);
    pq.push(arr[i]);
    while (slot_available > 0 && pq.size() > 0) {
      result.push_back(pq.top());
      pq.pop();
      slot_available--;
    }
  }

  sort(result.begin(), result.end(), [&](Job a, Job b) { return a.dead < b.dead; });
  for (int i = 0; i < result.size(); i++) cout << result[i].id << ' ';
  cout << endl;
}

int main() {
  int n;
  cin >> n;
  vector<Job> arr(n, {'a', 0, 0});
  for (int i = 0; i < n; i++) cin >> arr[i].id >> arr[i].dead >> arr[i].profit;
  printJobScheduling(arr);
  return 0;
}

Time Complexity: \(O(n \log n)\)
Auxiliary Space: \(O(n)\)
\(n\) - number of jobs

References and External Links#

Last update: 2023-10-05
Created: 2023-10-05