GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
558 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.

Task $T_1$ $T_2$ $T_3$ $T_4$ $T_5$ $T_6$ $T_7$ $T_8$ $T_9$
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

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

asked in Algorithms by Veteran (58.2k points)   | 558 views

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

Please refer the below URL for video lecture on this topic(Task Scheduling Problem).

2 Answers

+8 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:

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.

answered by Veteran (30.7k points)  
edited by
Can you explain why T4 and T6 are left out

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.

@vijay can you provide some reference material to understand this ?
+1 vote

 

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 Ti 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 atmost 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. T3 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 T9 with deadline 3 is similarly placed in  slot 2-3.

Task T7 with deadline 2 is placed in slot 1-.2.

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

Task T5 with deadline 4 is placed in slot 3-4.

Now comes task T4 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 T4 will be left out.

Task T8 with deadline 7 goes in slot 6-7.

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

Now all time slots are full.

So, Task T6 will be left out.

So, option (d) is the answer.

answered by Junior (765 points)  
edited by
Answer:

Related questions



Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2606 Points

  5. Debashish Deka

    2092 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1318 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1166 Points

  10. Sanjay Sharma

    1004 Points

Monthly Topper: Rs. 500 gift card

21,439 questions
26,753 answers
60,919 comments
22,929 users