GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
648 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 (59.2k points)   | 648 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

+9 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 (31.2k 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 ?
+2 votes

 

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 Active (1.3k points)  
edited by
Best Explanation. Thanks
Answer:

Related questions



Top Users Jun 2017
  1. Bikram

    2512 Points

  2. Hemant Parihar

    1480 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1334 Points

  5. Niraj Singh 2

    1311 Points

  6. rahul sharma 5

    1060 Points

  7. Rupendra Choudhary

    1042 Points

  8. Debashish Deka

    888 Points

  9. Arjun

    856 Points

  10. srestha

    836 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Niraj Singh 2

    1306 Points

  2. Bikram

    768 Points

  3. junaid ahmad

    502 Points

  4. akankshadewangan24

    252 Points

  5. joshi_nitish

    250 Points


23,325 questions
29,999 answers
67,196 comments
28,337 users