Anonymous user menu

Problem on Greedy Approach

We are given 10 tasks. The execution of task requires 1 unit of time. Each task Ti has profit pi and deadline di. Profit pi is earned if task Ti is completed before dith unit of time.

Task

T1

T2

T3

T4

T5

T6

T7

T8

T9

T10

Profit

15

22

x

18

25

12

24

18

20

15

Deadline

1

2

2

3

4

5

3

6

1

5

Suppose maximum total profit earned by scheduling above task is 129, then profit ‘x’ assigned to T3 is __________________.

 

Answer

Discuss: (Solution will be available on 7/6/2017)

4Comments
ALOK GUPTA @galok1001
8 Jul 2018 12:03 am
25
Naveen Kumar @naveenkr
9 Jul 2018 02:31 pm
@galok1001 how you solved, approach?
Neeraj Jetha @neerajjetha
9 Jul 2018 08:10 pm
25
Aditya Jain @markzuck241
5 Nov 2018 01:43 pm
if x is to be included in the max profit then it has to be included instead of other tasks whose deadline is 1
so T2 and T3 both will be considered for max profit

now the equation becomes:

22+x+24+25+15+18=129

solve it: x=25