edited by
4,920 views
23 votes
23 votes

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.

$$\begin{array}{|l|l|l|l|l|l|l|l|l|}\hline \textbf{Task}  &  \text{$T_1$ } & \text{$T_2$}& \text{$T_3$} & \text{$T_4$} & \text{$T_5$} & \text{$T_6$} & \text{$T_7$} & \text{$T_8$} & \text{$T_9$}   \\\hline \textbf{Profit}  &  \text{$15$ } & \text{$20$}& \text{$30$} & \text{$18$} & \text{$18$} & \text{$10$} & \text{$23$} & \text{$16$} & \text{$25$}   \\\hline  \textbf{Deadline} & \text{$7$} & \text{$2$} & \text{$5$} & \text{$3$} & \text{$4$}  & \text{$5$}  & \text{$2$}  & \text{$7$}  & \text{$3$} \\\hline \end{array}$$

What is the maximum profit earned?

  1. $147$
  2. $165$
  3. $167$
  4. $175$
edited by

3 Answers

Best answer
29 votes
29 votes

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:

$$\begin{array}{|l|l|l|l|l|l|l|l|l|}\hline \textbf{Task}  &  \text{$T_7$ } & \text{$T_2$}& \text{$T_9$} & \text{$T_4$} & \text{$T_5$} & \text{$T_3$} & \text{$T_6$} & \text{$T_8$} & \text{$T_1$}   \\\hline \textbf{Deadline}  &  \text{2} & \text{2}& \text{3} & \text{3} & \text{4} & \text{5} & \text{5} & \text{7} & \text{7} \\\hline \end{array}$$

$$0 \overset{T_7}{-} 1    \overset{T_2}{-} 2  \overset{T_9}{-}  3  \overset{T_5}{-}  4 \overset{T_3}{-}  5 \overset{T_8}{-}  6 \overset{T_1}{-}  7$$

Thus, $T_4$ and $T_6$ are left.

So, maximum profit will not include those of $T_4$ and $T_6$ and  will be $=15 + 20 +30 +18 + 16 + 23 + 25 = 147$ 

A is answer

edited by
2 votes
2 votes

First sort the tasks in descending orderof their profit.
T3 T9 T7 T2 T4 T5 T8 T1 T6
Now the maximum deadline given is 7.
So we will take Array of 7 elements. And will try to put the tasks starting from T3 to T6, upto their maximum deadline possible.

So T4 and T6 are left out.

 

We will now add the profits of the tasks we have put in the array.
30+25+23+20+18+16+15 = 147

Answer:

Related questions

53 votes
53 votes
5 answers
4
Kathleen asked Sep 22, 2014
18,927 views
double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } }The space complexity of the a...