GATE CSE 2005 | Question: 84a

Question

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?

• A. All tasks are completed

• B. $T_1$ and $T_6$ are left out

• C. $T_1$ and $T_8$ are left out

• D. $T_4$ and $T_6$ are left out

Comments

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

---

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$

Answer 1

$ \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&5& ✗ \\ \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.

Comments

@CSHuB

Sorry, but I am not understanding what you are trying to say. Have you gone through my comment

https://gateoverflow.in/1406/gate2005-84a?show=326225#c326225

---

Ayush Upadhyaya

in your table in the last T6 deadline is 5, not 2, please edit it.

 

---

it’s understandable.

Answer 2

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.

Comments

why this sequence is wrong ?

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

each task requires one unit of time,WHT DOES IT MEAN ?

---

@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

---

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.

Answer 3

This is Job Sequencing problem. It assumes:

• Every job takes 1 unit of time.
• If the job is finished within deadline, then only profit is earned.

How to solve?

1. Draw the time line as shown.
2. Sort tasks in decreasing order of profit. 
3. Take the task with highest profit and place it on deadline as far as possible.

 

So, T4 and T6 are left out.

Max profit = 20 + 23 + 25 + 18 + 30 + 15 + 16 = 147

Ans: D

Answer 4

First sort the tasks in descending order of 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.