GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
186 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 (76.3k points)   | 186 views
15 + 20 +30 +18 + 16 + 23 + 25 = 147

2 Answers

+5 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 (46.3k points)  
selected by
0 votes

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

answered by Boss (5.5k points)  
Answer:

Related questions



Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users