Skip to content
GATETECH
Official PYQ · 2005Q84bAlgorithm Design: Greedy TechniquesMCQ1 mark

GATE CS 2005 Q84b — Algorithm Design: Greedy Techniques

Explain with AI

We are given 99 tasks T1,T2,…,T9T_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 TiT_i has a profit PiP_i and a deadline did_i. Profit PiP_i is earned if the task is completed before the end of the dithd_i^{th} unit of time.

TaskT_1 T_2T_3T_4T_5T_6T_7T_8T_9Profit15 2030181810231625Deadline725345273\begin{array}{|l|l|l|l|l|l|l|l|l|}\hline \textbf{Task} & \text{$T\_1$ } & \text{$T\_2$}& \text{$T\_3$} & \text{$T\_4$} & \text{$T\_5$} & \text{$T\_6$} & \text{$T\_7$} & \text{$T\_8$} & \text{$T\_9$} \\ \hline \textbf{Profit} & \text{$15$ } & \text{$20$}& \text{$30$} & \text{$18$} & \text{$18$} & \text{$10$} & \text{$23$} & \text{$16$} & \text{$25$} \\ \hline \textbf{Deadline} & \text{$7$} & \text{$2$} & \text{$5$} & \text{$3$} & \text{$4$} & \text{$5$} & \text{$2$} & \text{$7$} & \text{$3$} \\ \hline \end{array}

What is the maximum profit earned?

Choose one option
View worked solution

Answer: A

To find the maximum profit, we use the greedy job scheduling algorithm. First, we sort the tasks in descending order of their profits:

Task T3T_3 T9T_9 T7T_7 T2T_2 T4T_4 T5T_5 T8T_8 T1T_1 T6T_6
Profit 30 25 23 20 18 18 16 15 10
Deadline 5 3 2 2 3 4 7 7 5

The maximum deadline is 77, so we have 77 available time slots: [0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7][0,1], [1,2], [2,3], [3,4], [4,5], [5,6], [6,7]. We schedule each task as late as possible before its deadline:

  • T3T_3 (Profit 30, Deadline 5): Scheduled in slot [4,5][4,5].
  • T9T_9 (Profit 25, Deadline 3): Scheduled in slot [2,3][2,3].
  • T7T_7 (Profit 23, Deadline 2): Scheduled in slot [1,2][1,2].
  • T2T_2 (Profit 20, Deadline 2): Slot [1,2][1,2] is occupied; scheduled in slot [0,1][0,1].
  • T4T_4 (Profit 18, Deadline 3): Slots [2,3][2,3], [1,2][1,2], and [0,1][0,1] are occupied; cannot be scheduled.
  • T5T_5 (Profit 18, Deadline 4): Scheduled in slot [3,4][3,4].
  • T8T_8 (Profit 16, Deadline 7): Scheduled in slot [6,7][6,7].
  • T1T_1 (Profit 15, Deadline 7): Scheduled in slot [5,6][5,6].
  • T6T_6 (Profit 10, Deadline 5): All slots up to 55 are occupied; cannot be scheduled.

The scheduled tasks are T2,T7,T9,T5,T3,T1,T_2, T_7, T_9, T_5, T_3, T_1, and T8T_8.

Maximum Profit=20+23+25+18+30+15+16=147\text{Maximum Profit} = 20 + 23 + 25 + 18 + 30 + 15 + 16 = 147

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Greedy Techniques questions