written 7.9 years ago by | • modified 7.9 years ago |
Step: 1
We will arrange the profits Pi in descending order, along with corresponding deadlines.
Step: 2
Create an array J [] which stores the jobs. Initially j [] will be
Step: 3
Add ith Job in array J [ ] at index denoted by its deadlines Di
First Job is P7, its deadline is 2.
Hence insert P7 in the array J [] at 2nd index.
Step: 4
Next Job is P3. Insert it in array J [] at index 4.
Step: 5
Next Job is P4. It has a deadline 3. Therefore insert it at index 3.
Step: 6
Next Job is P6, it has deadline 1. Hence Place P6 at index 1.
Step: 7
Next Job is P2, it had deadline 3. But as 3 is already occupied and there is no empty slot at index < J [3]. Just discard job P2. Similarly Job P1 and P5 will get discarded.
Step: 8
Thus the optimal sequence which we will obtain will be 6-7-4-3. The maximum profit will be 74.