job sequencing with deadline-programmingraja

 Aim: Write a program to implement Greedy algorithm for job sequencing with deadline. 

Software used: Dev C++

Description: 

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. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time. Print the sequence of job ID order to maximize total profit.

Program coding: 

#include<bits/stdc++.h>

using namespace std;

class job

{

public:

int jobid;

int deadline;

int profit;

};

bool mycompare(job *x,job *y)

{

return x->profit>y->profit; 

}

int maxProfit(job** obj,int n){

int max=0,profit=0;;

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);

int store[max]={0};

bool slot[max]={false}; 

for(int i=0;i<n;i++)

{

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;

}

}

}

cout<<"jobs sequence is:"<<"\t";

for(int i=0;i<max;i++)

{

if(slot[i])

cout<<store[i]<<"  ";

}

return profit;

}

int main()

{

int n,size,max,totalprofit=0;

cout<<"enter the no. of jobs:";

cin>>n;

job *obj[n]; 

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: