# Job sequencing problem

###### Problem statement

There are n jobs to be processed on a machine. Each job i has a deadline d_{i} >= 0 and profit p_{i} >= 0. p_{i} is earned if the job is completed by its deadline. Job is completed if it is processed on a machine for unit time. Only one job is processed at a time on the machine.

A feasible solution is a subset of jobs J such that each job is completed by its deadline. An optimal solution is a feasible solution with maximum value.

###### Solving algorithm
1. Sort   p_{i} in non-increasing order. So that, after sorting profit array looks like p_{1} >= p_{2} p_{n}
2. Add the next job i to the solution if i can be completed by its deadline. Assign i to the greatest (ie. r closest to the d_{i} ) time slot [r-1, r] such that 1<= r <= d_{i} and [r-1, r] is free.
3. Stop if all jobs are examined. Otherwise go to step 2.

Time complexity: O(n2)

Code Implementation

//
//  main.cpp
//  Job sequencing
//
//  Created by Himanshu on 14/08/21.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5;

struct node {
int p, d; // p = profit, d = deadline
};

bool cmp (const struct node &a, const struct node &b) {
return a.p> b.p;
}

void solve (int p[], int d[]) {

struct node q[N];
int slot[N] = {0};
int ans = 0;
vector<int> sol;

for (int i=0; i<N; i++) {
q[i].p = p[i];
q[i].d = d[i];
}

sort(q, q+N, &cmp);

for (int i=0; i<N; i++) {
if (slot[q[i].d-1] == 0) {
sol.push_back(i);
slot[q[i].d - 1] = 1;
} else {
int j = q[i].d - 1;
while (j>=0 && slot[j] != 0) {
j--;
}

if (j >= 0) {
ans += q[i].p;
sol.push_back(i);
slot[j] = 1;
}
}
}

cout<<"Job selected\n";
for (int i=0; i<sol.size(); i++) {
cout<<q[sol[i]].p<<" ";
}

cout<<"\nProfit: "<<ans<<"\n";
}

int main() {
int p[] = {10, 5, 20, 15, 1};
int d[] = {1, 3, 2, 2, 3};

solve(p, d);

return 0;
}



Output

Job selected
20 15 5
Profit: 40

Here’s a working example: Ideone