First time here? Checkout the FAQ!
+6 votes

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.9k points)   | 692 views

Question has been splitted. Please check the below URL for the B part

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.4k 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.4k points)  
edited by
Best Explanation. Thanks

Related questions

Top Users Jul 2017
  1. Bikram

    5258 Points

  2. manu00x

    3078 Points

  3. joshi_nitish

    1882 Points

  4. Debashish Deka

    1874 Points

  5. Arjun

    1814 Points

  6. pawan kumarln

    1336 Points

  7. Hemant Parihar

    1314 Points

  8. Shubhanshu

    1136 Points

  9. Arnab Bhadra

    1124 Points

  10. Tesla!

    1056 Points

24,122 questions
31,124 answers
29,437 users