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$

---

sort in descending order of Profits , then place the jobs at maximum deadline possible

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

Ayush Upadhyaya

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

 

---

it’s understandable.

---

best explaination sir

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

@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.

---

Let’s say there are three jobs A, B, and C:

Job	Deadline	Profit
A	1	5
B	2	10
C	2	15

If we sort the jobs according to deadline (and use profit as a tie-breaker), the order will be A, B, C.
Now, we choose jobs A and C, giving a total profit of 20.
Here, job B is discarded because job A has a shorter deadline — we compared deadlines first.

However, to get the maximum profit, the ideal selection is B and C, which gives a total profit of 25.
In this case, we discard A because its profit is smaller than B’s.
That’s why we should compare profits first, not deadlines.

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.

Answer 5

Tasks and their time chart will be as follows:

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

The tasks T4 and T6 are left out.