Redirected
edited by
922 views
1 votes
1 votes

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 __________________.

edited by

2 Answers

Best answer
1 votes
1 votes

First we need to arrange the tasks according to deadline and then profit.

T9  T1 T3 T2 T7 T4 T5 T10 T6 T8
20 15 X 22 24 18 25 15 12 18
1 1 2 2

3

3 4 5 5 6

Then selecting the tasks based on their deadlines,

T9 + T3 + T7 + T5 + T5 + T10 + T8 = 129

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

x = 129 - 104

x = 25.

Hence 25 is the required value for maximum total profit earned by scheduling above task is 129

selected by
1 votes
1 votes

we need max so 

deadline1 -- 22 (T2 max so this can also be added)

2 --- x

3---- 24

4--- 25

5--- 15

6--- 18 so adding them all should be equal to 129 as the max with respective local are selected to give global max

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

so x = 25

Answer:

Related questions

2 votes
2 votes
3 answers
1
4 votes
4 votes
3 answers
2
Lakshman Bhaiya asked Nov 10, 2018
12,278 views
If job $J=(J_{1},J_{2},J_{3},J_{4})$ are given their processing time $T_{i}=(1,1,2,3)$ and deadline are $D_{i}=(3,4,2,3)$ maximum how many job can be done$?$$A)1$ ...
2 votes
2 votes
2 answers
3
iita asked Dec 16, 2016
661 views
2 votes
2 votes
1 answer
4
A_i_$_h asked Oct 9, 2017
1,190 views
Given that ready contains at some point of time a maximum of n process , the time complexity to schedule and dispatch a process from ready queue onto CPU using priority ...