The Gateway to Computer Science Excellence
+20 votes
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$
in Algorithms by Veteran (105k points)
edited by | 1.1k views
0
15 + 20 +30 +18 + 16 + 23 + 25 = 147

2 Answers

+25 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:

$$\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

by Veteran (63k points)
edited by
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

@Prashant., quick question. When you said in your answer.

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 ?

+6 votes

Plz refer here.

by Boss (15k points)
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,560 comments
105,390 users