The Gateway to Computer Science Excellence

+20 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?

- $147$
- $165$
- $167$
- $175$

+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

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 ?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,385 answers

198,560 comments

105,390 users