 ### C++ Job Sequencing with deadline (Greedy approach)

Job sequencing is of the classic problems that can be solved using greedy algorithm.

Here we are given an array of jobs having a specific deadline associated with a profit, if the job is done within the deadline.

Our task is to assign jobs in a schedule such that, only one job is done at a time and profit is maximized.

### OUR WAY OF APPROACH

`We have to sort the jobs in descending order of profit.Next, we have to iterate through the job and select slots.Slot i is selected if,                    a. Slot i is not previously selected.	      b. i < deadline	      c. i should be just less than the deadline if possible (so that other slots can be optimized).If no such slot is possible, ignore the job.`

### Input:

`JobID  Deadline   Profit  1           2          20     2           2          15  3           1          10    4           3           5  5	        3           1`

### Output:

`Job sequenced in order: 2 1 4`

### Explanation:

Here the maximum deadline is 3. Maximum profit is given by Job1. And since it has deadline 2 it occupies position2 in the job sequence. Next maximum profit is given by Job2. Since position 2 is occupied by Job1, it occupies the next position to the front of 2 ie. position1. We do not take Job3 into consideration because, it has deadline 1 and position 1 is already filled with a better job. Next, Job4 is taken and placed in position3, since it has maximum profit compared to Job5.

# CODE:

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

//structure for holding values
typedef struct Job
{
int jobNum;
int profit;
}Job;

bool compare(Job aJob b);
void jobSequencing(Job input[], int num);

int main()
{
int num;
cin >> num;
Job input[num];
// inputing the values
for (int i = 0; i < num; i++)
{
cin >> input[i].jobNum;
cin >> input[i].profit;
}

jobSequencing(input, num);
}

// a custom comparison function for arrenging jobs in decreasing order of profit
bool compare(Job aJob b)
{
return (a.profit > b.profit);
}

// main part of code where job sequencing happens
void jobSequencing(Job input[], int num)
{
sort(inputinput + numcompare);

int result[num];

bool slot[num];
// setting all values in slot as false
memset(slot, 0sizeof(slot));

for (int i = 0; i < num; i++)
{
for (int j = min(numinput[i].deadline)-1; j >= 0; j--)
{
if(slot[j] == false)
{
result[j] = i;
slot[j] = true;
break;
}
}
}

cout << "Job sequenced in order: ";
for (int i=0; i<num; i++)
{
if (slot[i] == true)
cout << input[result[i]].jobNum << " ";
}
} 