Job sequencing with dead line

Job sequencing with dead line is yet another greedy approach.

Given a set of jobs with their profits and deadlines, the idea is to find the subset of jobs that will produce maximum profit.

Let us take an example to easily understand how it works. Assume each job takes one unit time for execution.

Consider 4 jobs, with profits 100,10,15,27 respectively and deadline 2,1,2,1 respectively.

Job	1	2	3	4
Profit	100	10	15	27
Deadline	2	1	2	1

job 2 or 4 if taken should be completed in unit time 1. so only one can be taken among them. let us take job 4 as it gives more profit. Now in the unit time 2 we have to take job 1 as it gives more profit.Therefore we can take the best sequence as Maximum deadline in the given set is 2. so within 2 units of time we should identify the jobs if taken,will produce the maximum profit. In 2 units of time only 2 jobs can be completed. So which two jobs?

0               1               2        <-- Time

Job 4

Job 1

Consider one more example for the same problem.

Job	1	2	3	4	5
Profit	20	15	10	5	1
Deadline	2	2	1	3	3

So within 3 units of time we can complete 3 jobs. The best sequence will be

0               1               2                3    <-- Time

Job 1

Job 2

Job 4

and the profit will be 45. If more number of jobs are given then it may be a good idea to arrange the jobs in non increasing order of their profits and then identify the sequence.