The Gateway to Computer Science Excellence
+22 votes
2.6k 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}$$

Are all tasks completed in the schedule that gives maximum profit?

  1. All tasks are completed

  2. $T_1$ and $T_6$ are left out

  3. $T_1$ and $T_8$ are left out

  4. $T_4$ and $T_6$ are left out

in Algorithms by Veteran (52.2k points)
edited by | 2.6k views
0

Question has been splitted. Please check the below URL for the B part https://gateoverflow.in/82514/gate2005-84b

0

An example to illustrate properly:

task j1 j2 j3 j4
profit 250 300 150 350
deadline 2 1 2 1

Sort all jobs in descending order of profit:

task j4 j2 j1 j3
profit 350 300 250 150
deadline 1 1 2 2

Maximum deadline=2. So max jobs possible =2

task

all jobs are fighting(even j1 &

j3 fights in order to

get completed within less time

but j2 & j4 begging). take j4

Only j1 & j3 is fighting. j1 more profit,take that
deadline 1 (or more than 1) 2 (or more than 2)

Similarly approach the given question:

task $t_{2}$ $t_{7}$ $t_{9}$ $t_{5}$ $t_{3}$ $t_{1}$ $t_{8}$
deadline 1 2 3 4 5 6 7

$Ans: t_{4}\ \&\ t_{6}\ are\ left\ out$

2 Answers

+28 votes
Best answer

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

Step -1 Sort the tasks in decreasing order of profit and if any conflict arises between two or more tasks,resolve them by sorting them on basis of having greater deadline first(Because we have more time to complete the task with greater deadline and same profit).

Step 2- Since Maximum deadline given is $7$, so we consider we have 7 time slots ranging from $0-7$ where a task $T_i$ having deadline say $2$ can be filled in slots either $0-1$ or $1-2$ and not beyond $2$ because this task has deadline of $2$ time units, so this task has to be completed by at most time $T=2$.

Now according to question, since Each task completes in Unit time, so a single tasks takes only one slot as shown.

Now Take the first task in the list i.e. $T_3$ which has a deadline of $5$, so it can be completed in maximum $5$ time units, so place it in slot $4-5$ which is the maximum deadline by which this task can be completed.

Task $T_9$ with deadline $3$ is similarly placed in  slot $2-3$.

Task $T_7$ with deadline $2$ is placed in slot $1-2$.

Now for task $T_2$ having deadline $2$ can be placed in either $0-1$ or $1-2$ (Occupied by $T_7$). So $T_2$ will occupy slot $0-1$.

Task $T_5$ with deadline $4$ is placed in slot $3-4$.

Now comes task $T_4$ which has deadline $3$ can be put in slots $0-1$ or $1-2$ or $2-3$ and not beyond that.Unfortunately, all such slots are occupied so $\bf{T_4}$ will be left out.

Task $T_8$ with deadline $7$ goes in slot $6-7$.

Task $T_1$ with deadline $7$ can be placed in  slot $5-6$.

Now all time slots are full.

So, Task $\bf{T_6}$ will be left out.

So, option (d) is the answer.

by Boss (27.6k points)
edited by
+1
Best Explanation. Thanks
+16 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:

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

T4 and T6 left out
 

D is answer.

by Boss (31.2k points)
reshown by
0
Can you explain why T4 and T6 are left out
+1

Since we have to be greedy about profit, so first we have to choose a task with max profit considering its deadline.

Time 1 2 3 4 5 6 7
Order Of Task T7 T2 T9 T5 T3 T8 T1
Profit 23 20 25 18 30 16 15
deadline 2 2 3 4 5 7 7

TOTAL MAXIMUM PROFIT = (23 + 20 + 25 + 18 + 30 + 16 + 15) = 147.

0
@vijay can you provide some reference material to understand this ?
0
why this sequence is wrong ?

T2-------T7------T9------T5---------T3--------T1------T8?????

each task requires one unit of time,WHT DOES IT MEAN ?
0
@set2018 watch the video provided by @Ayush.. i bet everything will be crystal clear...

and each and every task T1,T2,.....Tn takes exactly 1 unit of time to execute
0
Though you arrive at the same answer, your explanation is faulty. Consider the case when T4 has a huge profit (huge enough to be greater than the sum of all other profits, say). In that case, T4 must always be included in the schedule. But your algorithm will always leave T4 out because you are sorting on deadline first and then profit. We have to be greedy, yes, but the correct way is to sort on profit first and then deadline.

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,648 questions
56,457 answers
195,312 comments
100,145 users