1.1k 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.

$$\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 | 1.1k views
0
15 + 20 +30 +18 + 16 + 23 + 25 = 147

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$

by Veteran (63k points)
edited
0
why this sequence is wrong ?

T2-------T7------T9------T5---------T3--------T1------T8?????
0
though answer is correct but the actual allocation shown in the answer is wrong,1st cell should have T2 and 2nd slot T7 (rest same).
0

The most important statement in question is
Each task requires 1 unit of time
This shows we can greedly choose the better task..

Why is it so? Why we can greedly choose then only ?