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
- Sort p_{i} in non-increasing order. So that, after sorting profit array looks like p_{1} >= p_{2} … p_{n}
- 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. - 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) {
ans += q[i].p; //Adding current job's profit to answer
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
One thought on “Job sequencing problem”