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 ?

      A) All tasks are completed

      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

 

Answer

(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)

0Comment