Given an array of jobs where every job has a deadline and a profit. Profit can be earned only if the job is finished before the deadline

At time 0:

Select maximum profit one with deadline at most 2
Job id: 3, deadline: 2, valid choice, process the job
Profit at time 0 : 60

At time 1:

Select maximum profit one from remaining jobswith deadline at most 2
Job id: 4, deadline: 2, valid choice, process the job
Profit at time 1 : 60+30
That’s why can’t choose job with ID 5 & 2

At time 2:

Select maximum from remaining one with deadline greater than 2
Job id: 6, deadline: 4, valid choice, process the job
Profit at time 2 : 60+30+80

At time 3:

Select job
With job id: 1, deadline : 4, valid choice, process the job
Job sequence : 3 4 6 1
Finally total profit= 60+30+80+30=200

No other choice could have resulted better (you can check it!!!!). Thus the solution is optimized and we have found the maximum solution.

Now, revise what we have done. We have actually sorted the job table according to max profit & then have made the local best choice at each iteration to reduce the problem size & ultimately to reach the goal. Simply speaking, we have used the greedy technique intuitively & greedy algorithm has successfully solved the job sequencing problem.

Now to code simply follow the below steps which are nothing but what we did solving the previous example:

1. Create a class to define jobs

class job
{
	public:
	int jobid;  //job id
	int deadline; //deadline
	int profit; //profit of the job
};

1. To take input we have used the concept of array of pointers to the job objects. job *obj[n]; //array of pointer to jobs(jobs namely)
2. maxProfit function()
   • Sort all jobs in decreasing order of profit.
     To do this we have defined our own compare function & used STL sort.

   bool mycompare(job *x,job *y)//boolean function
   {
   	//sort as per decreasing profite
       return x->profit>y->profit; 
   }
   sort(obj,obj+n,mycompare);
   

   • Find the maximum deadline, let it be max.
   • Create store[max] to store job sequence
     Create slot[max] to mark occupied slots
   • For i=0:no of jobs

   // now pick the job with max deadline from 
   // that deadline traverse array backto find an empty slot
   for(int j=(obj[i]->deadline)-1;j>=0;j--)
   {
   	if(slot[j]==false){	// slot is empty
   				
   	// count the total profit
   		profit+=obj[i]->profit;
   		store[j]=obj[i]->jobid;
   		slot[j]=true;
   		break;
   	}
   	
   }
   

   • Print the store array to find job sequence and print profit which is maximum profit output

C++ implementation of Job sequencing problem

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

// define the class for the job
class job
{
	public:
		int jobid;
		int deadline;
		int profit;
};
// our compare function to sort
bool mycompare(job *x,job *y)//boolean function
{
	//sort as per decreasing profit
	return x->profit>y->profit; 
}

int maxProfit(job** obj,int n){
	int max=0,profit=0;;
	//find maximum deadline
	for(int i=0;i<n;i++){
		if(i==0){
			max=obj[i]->deadline;
		}
		else{
			if(obj[i]->deadline>max)
				max=obj[i]->deadline;
		}
	}
	
	sort(obj,obj+n,mycompare);
	// create array of max deadline size
	int store[max]={0};	// empty array initially
	bool slot[max]={false}; //all slots empty initially
	for(int i=0;i<n;i++)
	{	
		// now pick the job with max deadline and from 
		// that deadline traverse array back to find an empty slot
		for(int j=(obj[i]->deadline)-1;j>=0;j--)
		{
			if(slot[j]==false)	// slot is empty
			{	
				// count the total profit
				profit+=obj[i]->profit;
				store[j]=obj[i]->jobid;
				slot[j]=true;
				break;
			}
		}
	}
	// printing the job sequence
	cout<<"jobs sequence is:"<<"\t";
	for(int i=0;i<max;i++)
	{	
		if(slot[i])
			cout<<store[i]<<"  ";
	}
	return profit; //return profit
}

int main()
{	
	int n,size,max,totalprofit=0;
	cout<<"enter the no. of jobs:";
	cin>>n;
	job *obj[n]; //array of pointer to jobs(jobs namely) 
	// user input and finding maximum deadline
	for(int i=0;i<n;i++)
	{	
		obj[i]=(job*)malloc(sizeof(struct job));
		cout<<"enter jobid,deadline and profit of job "<<i+1<<endl;

		cin>>obj[i]->jobid;
		cin>>obj[i]->deadline;
		cin>>obj[i]->profit;
	}

	totalprofit=maxProfit(obj,n); //total profit
	cout<<"\ntotal profit is "<<totalprofit<<"\n";
	
	return 0;	
}

Output

enter the no. of jobs:6
enter jobid,deadline and profit of job 1
1 4 30
enter jobid,deadline and profit of job 2
2 2 20
enter jobid,deadline and profit of job 3
3 2 60  
enter jobid,deadline and profit of job 4
4 2 30  
enter jobid,deadline and profit of job 5
5 1 10  
enter jobid,deadline and profit of job 6
6 4 80  
jobs sequence is:       4  3  1  6
total profit is 200