Solve the following Job Sequencing with deadlines problem. N = 7 Profits (P1, P2, P3, P4, P5, P6, P7) = {3, 5, 20, 18, 1, 6, 30} Deadlines (D1, D2, D3, D4, D5, D6, D7) = {1, 3, 4, 3, 2, 1, 2}

3.5kviews

written 8.1 years ago by

sagarnarkar • 2.1k

• modified 8.1 years ago

Step: 1

We will arrange the profits Pi in descending order, along with corresponding deadlines.

enter image description here

Step: 2

Create an array J [] which stores the jobs. Initially j [] will be enter image description here

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. enter image description here

Step: 4

Next Job is P3. Insert it in array J [] at index 4.

enter image description here

Step: 5

Next Job is P4. It has a deadline 3. Therefore insert it at index 3. enter image description here

Step: 6

Next Job is P6, it has deadline 1. Hence Place P6 at index 1.

enter image description here

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.

ADD COMMENT EDIT