# GATE2005-84a

4k 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?

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

edited
0

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

1

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$

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

edited by
1
Best Explanation. Thanks
0
$\mathbf {T_7}$ should come in place of $\mathbf{T_2}$
0
@satbir

@kushagra

0

@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

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

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

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

## Related questions

1
1.4k 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 ... $} & \text{$7$} & \text{$3$} \\\hline \end{array}$ What is the maximum profit earned? $147$ $165$ $167$ $175$
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one ... minimum weighted spanning tree a weighted shortest path from $s$ to $t$ an Euler walk from $s$ to $t$ a Hamiltonian path from $s$ to $t$
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one vertex in ... tree of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(|V|^2\right)$ $O\left(|E|+|V|\log |V|\right)$ $O\left(|V|\log|V|\right)$ $O\left(\left(|E|+|V|\right)\log|V|\right)$