We are given 9 tasks T1, T2.... T9. The execution of each task requires one…

2005

We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time. 

Task     T1  T2	 T3  T4  T5  T6	 T7 T8  T9
Profit   15  20	 30  18  18  10	 23 16  25
Deadline 7   2 	 5   3 	 4   5 	 2  7   3

What is the maximum profit earned?

  1. A.

    147

  2. B.

    165

  3. C.

    167

  4. D.

    175

Attempted by 99 students.

Show answer & explanation

Correct answer: A

Solution:

Key idea: Sort tasks by profit (highest first) and place each task into the latest available time slot on or before its deadline.

  • Sort tasks by profit:

    T3 (profit 30, deadline 5), T9 (25, d=3), T7 (23, d=2), T2 (20, d=2), T4 (18, d=3), T5 (18, d=4), T8 (16, d=7), T1 (15, d=7), T6 (10, d=5).

  1. Place T3 (30, d=5) into latest free slot ≤5 → slot 5.

  2. Place T9 (25, d=3) into latest free slot ≤3 → slot 3.

  3. Place T7 (23, d=2) into latest free slot ≤2 → slot 2.

  4. Place T2 (20, d=2) into latest free slot ≤2; slot 2 is taken, so use slot 1.

  5. T4 (18, d=3) cannot be placed because slots 1–3 are already filled.

  6. Place T5 (18, d=4) into latest free slot ≤4 → slot 4.

  7. Place T8 (16, d=7) into latest free slot ≤7 → slot 7.

  8. Place T1 (15, d=7) into latest free slot ≤7; slot 7 is taken, so use slot 6.

  9. T6 (10, d=5) cannot be placed because slots 1–5 are filled.

Selected schedule (slots 1 to 7): slot 1 = T2 (20), slot 2 = T7 (23), slot 3 = T9 (25), slot 4 = T5 (18), slot 5 = T3 (30), slot 6 = T1 (15), slot 7 = T8 (16).

Total profit = 20 + 23 + 25 + 18 + 30 + 15 + 16 = 147.

Therefore the maximum profit that can be earned under the deadlines and one-task-per-time-unit constraint is 147.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir