First time here? Checkout the FAQ!
+8 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 (64.6k points)   | 829 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

+6 votes
Best answer


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.9k points)  
selected by
Best Explanation. Thanks
+11 votes

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 (32.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 ?

Related questions

Top Users Sep 2017
  1. Habibkhan

    6826 Points

  2. Arjun

    2310 Points

  3. Warrior

    2302 Points

  4. nikunj

    1980 Points

  5. A_i_$_h

    1922 Points

  6. manu00x

    1750 Points

  7. rishu_darkshadow

    1744 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points

26,033 questions
33,618 answers
31,066 users