##### GATE 2005 Example on Greedy Algorithms

We are given 9 tasks $T_1, T_2, T_3, .....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

(1) Are all tasks completed in the schedule that gives maximum profit ?

B) $T_1 \ \ and \ \ T_2$ are left out

C) $T_1 \ \ and \ \ T_8$ are left out.

D) $T_4 \ \ and \ \ T_6$ are left out.

(2) What is the maximum profit earned ?

A) 147

B) 165

C) 167

D) 175

(1)

$\underline{\text{Step - I}}$:  Arrange the the task in increasing order of Deadline and then Profit:

 Task $T_7$ $T_2$ $T_9$ $T_4$ $T_5$ $T_3$ $T_6$ $T_8$ $T_1$ Deadline 2 2 3 3 4 5 5 7 7

$\underline{\text{Step - II}}$ : Now, pick task one by  one and execute it (NOTE: Each task takes 1 unit of time )

 Task $T_7$ $T_2$ $T_9$ $T_5$ $T_3$ $T_8$ $T_1$ Time Period of Execution 0 to 1 1 to 2 2 to 3 3 to 4 4 to 5 5 to 6 6 to 7

Hence, Except  $T_4 \ \ and \ \ T_6$  , all other task are completed. Ans (D)

(2)

Maximum Profit = $P_7 + P_2+ P_9 + P_5 + P_3 + P_8 + P_1$

$\hspace{30mm} = 23 + 20 +25+18+ 30 + 16+15$

$\hspace{30mm} = 147$

Hence, Ans (A)