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

GATE CS 2005 Q84a — 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}

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

Choose one option
View worked solution

Answer: D

To find the schedule that maximizes profit, we use the greedy Job Sequencing with Deadlines 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 time slots: [0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[0,1], [1,2], [2,3], [3,4], [4,5], [5,6], and [6,7][6,7]. We attempt to schedule each task in its latest possible free slot before or at its deadline:

  • T3T_3 (deadline 5): Scheduled in slot [4,5][4, 5].
  • T9T_9 (deadline 3): Scheduled in slot [2,3][2, 3].
  • T7T_7 (deadline 2): Scheduled in slot [1,2][1, 2].
  • T2T_2 (deadline 2): Slot [1,2][1,2] is occupied. Scheduled in slot [0,1][0, 1].
  • T4T_4 (deadline 3): Slots [2,3][2,3], [1,2][1,2], and [0,1][0,1] are all occupied. T4T_4 cannot be scheduled.
  • T5T_5 (deadline 4): Scheduled in slot [3,4][3, 4].
  • T8T_8 (deadline 7): Scheduled in slot [6,7][6, 7].
  • T1T_1 (deadline 7): Slot [6,7][6,7] is occupied. Scheduled in slot [5,6][5, 6].
  • T6T_6 (deadline 5): All slots ≤5\le 5 are occupied. T6T_6 cannot be scheduled.

Thus, 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. The tasks left out are T4T_4 and T6T_6.

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

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