GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
250 views

We are given 9 tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the $d_i^{th}$ unit of time.

Task $T_1$ $T_2$ $T_3$ $T_4$ $T_5$ $T_6$ $T_7$ $T_8$ $T_9$
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

What is the maximum profit earned?

  1. 147
  2. 165
  3. 167
  4. 175
asked in Algorithms by Veteran (79k points)   | 250 views
15 + 20 +30 +18 + 16 + 23 + 25 = 147

2 Answers

+7 votes
Best answer

The most important statement in question is 

each task requires one unit of time

This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

Task T7 T2 T9 T4 T5 T3 T6 T8 T1
Deadline 2 2 3 3 4 5 5 7 7

       0 --T7 -- 1  --  T2  --  2  --  T9  --  3  --  T5  --  4  --  T3 --  5 --  T8 --  6  --  T1 --  7 

so we know that T4 and T6 are left

so profit will not include T4 and T6 = 15 + 20 +30 +18 + 16 + 23 + 25 = 147 

A is answer

 

answered by Veteran (48.4k points)  
selected by
0 votes

plz go through following links:https://www.youtube.com/watch?v=yHsDLU3ZqNM

answered by Boss (6.5k points)  
Answer:

Related questions



Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users