self doubt

Question

i am getting 100+35+50=185 is it correct ???

Comments

100+50+25 = 175

---

how??? explain

---

First take high profitable job and place it at it's deadline,

why because with in a deadline you must get that profit.

if your doubt is why to place at deadline? i will take at starting ?

then consider this example

J1 deadline is 1 and profit is 50

J2 deadline is 2 and profit is 100

therefore if you take J2 as first choice then you can't complete J1 ===>profit is 100 only

if you take J2 at it's deadline choice then you can complete J1 also ===>profit is 100+50

Answer 1

Always put maximum profit job as farthest as possible. Sort them according to their profit and total time is maximum in deadline.

Job	J2	J3	J5	J1	J4
Deadline	1	2	1	3	2
Profit	100	50	35	25	25

Now as you can see J2 is having highest profit and it should be completed in 1st time slot(not after that).

So first take J2 for time slot 1. after that J3 is having highest profit and it will complete in 2nd time slot. (J3 can be completed before 2 but not after that) now J5 can't be completed because 1 slot is already taken by J2 so only J1 can execute in 3rd time slot.

So total profit= 100+50+25 =175

 

Answer 2

first short the jobs with respect to their profit

                        j2,j3,j5,j4=j1

And short jobs with respect to their deadline early job first

                       j2=j5,j3=j4,j1

initialize a variable profit=0, and a stack for holding done jobs.

step 1: Take max profit job with minimum deadline (means early job).

stack=j2

profit=100

step 2: Take next max profit job in remaning with minimum deadline (means early job).

stack=j2,j3

profit=100+50

step 3: Take next max profit job in remaining with minimum deadline (means early job).

stack=j2,j3,j1

profit=100+50+25

final profit is 175