Greedy scheduling is common in Algorithms. Activity selection asks for the maximum number of non-overlapping intervals; job sequencing packs profitable unit-time jobs into legal slots. Five of the 12 below carry previous-year labels (GATE 2003, GATE 2005 in two parts, UGC NET December 2015 and ISRO 2007); the rest are practice questions on the same patterns. Two rules carry most of the work: earliest finish time for activity selection, highest profit first for job sequencing. Attempt each question before reading its answer.
1. Activity selection and job sequencing: the rule, compatibility and complexity
Q1. Activity selection rule
In the activity selection problem, activities are selected based on:
(a) Earliest start time (b) Shortest duration (c) Least resources (d) Earliest finish time
Answer: (d) Earliest finish time. Finishing early leaves the most room for later activities. Earliest start chooses (1, 10) and blocks (2, 3) and (3, 4), while earliest finish selects both short activities. Shortest duration is not a safe rule either.
Q2. UGC NET Paper 2 December 2015
In Activity-Selection problem, each activity i has a start time s_i and a finish time f_i where s_i <= f_i. Activities i and j are compatible if :
(a) s_i >= f_j (b) s_j >= f_i (c) s_i >= f_j or s_j >= f_i (d) s_i >= f_j and s_j >= f_i
Answer: (c). Compatible intervals do not overlap. Either i starts after j finishes, or j starts after i finishes, so the connector must be OR. Equality is allowed because an activity may start exactly when another finishes.
Q3. Job sequencing complexity
The time complexity of job sequencing with deadlines, when implemented with a greedy algorithm, is
(a) O(n) (b) O(n log n) (c) O(n^2) (d) O(n^3)
Answer: (b) O(n log n). Sorting jobs by profit dominates when slot assignment is efficient. A naive backward scan for every job can take O(n^2) in the worst case, but the accepted textbook answer for the greedy method is the O(n log n) sorting bound.
2. Counting non-overlapping activities: one MCQ, one NAT
Q4. Select the maximum activities
You are given 4 activities with start and finish times: A1: (1, 3) A2: (2, 5) A3: (4, 6) A4: (6, 7). What is the maximum number of non-overlapping activities that can be selected using the greedy approach?
(a) 2 (b) 3 (c) 4 (d) 1
Answer: (b) 3. Finish times 3, 5, 6, 7 already put the activities in A1, A2, A3, A4 order. Pick A1. Reject A2 because 2 < 3, pick A3 because 4 >= 3, then pick A4 because 6 >= 6. The selection {A1, A3, A4} has 3 activities.
Q5. Maximum tasks on one machine
Consider the following tasks to be scheduled on a single machine. A task can be selected only if it does not overlap with the previously selected task; a task finishing at time t may be followed by a task starting at time t. Tasks with (start time, finish time): T1 (1, 4), T2 (2, 4), T3 (1, 5), T4 (3, 7), T5 (4, 6), T6 (7, 8), T7 (6, 7). What is the maximum number of tasks that can be completed?
Answer: 4. Sort by finish time: T1, T2, T3, T5, T4, T7, T6. Pick T1, skip T2 and T3, pick T5 at 4, skip T4, then pick T7 at 6 and T6 at 7. The sequence T1 -> T5 -> T7 -> T6 has 4 tasks.
3. GATE 2003: minimum rooms is the same trick reversed
Q6. Minimum rooms
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: 'as bs cs ae ds ce es fs be de gs ee fe hs ge he'. Here, xs denotes the starting time and xe denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
(a) 3 (b) 4 (c) 5 (d) 6
Answer: (b) 4. Track starts as +1 and ends as -1: as 1, bs 2, cs 3, ae 2, ds 3, ce 2, es 3, fs 4, be 3, de 2, gs 3, ee 2, fe 1, hs 2, ge 1, he 0. The peak is 4, when B, D, E and F overlap, so 4 rooms are needed. Activity selection counts how many intervals avoid each other; room counting measures how many cannot. Same interval set, read from opposite ends.
4. Job sequencing basics: is a schedule feasible at all?
Q7. ISRO 2007 feasibility
Consider a job scheduling problem with 4 jobs J1, J2, J3, J4 and with corresponding deadlines: (d1, d2, d3, d4) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job's deadline?
(a) J2, J4, J1, J3 (b) J4, J1, J2, J3 (c) J4, J2, J1, J3 (d) J4, J2, J3, J1
Answer: (b). In J4, J1, J2, J3, job J2 sits in position 3 and finishes at time 3, but its deadline is 2. Every other option places both deadline-2 jobs (J2 and J4) in the first two slots. For unit-time jobs the test is simply this: every position must be no greater than the deadline of the job in it. The same question also appears as a BEL 2007 paper item, so expect it to come back.
5. The GATE 2005 classic: who gets left out, and how much do you earn
Use this shared data for Q8 and Q9:
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 di-th 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 |
Q8. Are all tasks completed?
Are all tasks completed in the schedule that gives maximum profit?
(a) All tasks are completed (b) T1 and T6 are left out (c) T1 and T8 are left out (d) T4 and T6 are left out
Answer: (d) T4 and T6 are left out. The largest deadline is 7, so at most 7 of the 9 tasks can run and at least two must be dropped. T2, T7 and T9 have deadlines 2, 2 and 3 and all three out-earn T4, so they take slots 1, 2 and 3 and leave T4 (deadline 3) with nowhere legal to go. T6 has the lowest profit of all nine at 10, and slots 1 to 5 are full by the time it is reached.
Q9. What is the maximum profit?
What is the maximum profit earned?
(a) 147 (b) 165 (c) 167 (d) 175
Answer: (a) 147. Sort by descending profit: T3, T9, T7, T2, T4, T5, T8, T1, T6. Place each as late as possible: T3 -> 5, T9 -> 3, T7 -> 2, T2 -> 1, T4 dropped, T5 -> 4, T8 -> 7, T1 -> 6, T6 dropped. Slots 1 to 7 are T2, T7, T9, T5, T3, T1, T8. The profit is 20 + 23 + 25 + 18 + 30 + 15 + 16 = 147.
6. Three profit NATs to build speed
Treat these three as timed drills, under three minutes each. Timed sets like these are what GATE Test Series, Mocks & Topic-wise Tests is built for.
Q10. Seven-job maximum profit
The optimal solution generated by the job sequencing with deadlines with n = 7, p1, p2, ..., p7 = (8, 10, 25, 23, 6, 11, 35), d1, d2, ..., d7 = (1, 3, 4, 3, 2, 1, 2) is _____?
Answer: 94. Place p7(35, d2) -> 2, p3(25, d4) -> 4, p4(23, d3) -> 3 and p6(11, d1) -> 1. All legal slots for the remaining jobs are full. Total = 35 + 25 + 23 + 11 = 94.
Q11. Four-task maximum profit
If we have four tasks T1, T2, T3, T4, having deadline D1 = 2, D2 = 1, D3 = 2, D4 = 1, and profit P1 = 100, P2 = 10, P3 = 27, P4 = 15, find the maximum profit possible?
Answer: 127. Put T1(100, d2) in slot 2 and T3(27, d2) in slot 1. T4 and T2 both need the occupied slot 1, so they are dropped. Total = 100 + 27 = 127.
Q12. Five-job maximum profit
Given the jobs, their profit and deadline. Assume all jobs arrive at time 0 and burst time is 1. What is the maximum profit that we can make?
Job 1: deadline 1, profit 10. Job 2: deadline 2, profit 15. Job 3: deadline 2, profit 20. Job 4: deadline 3, profit 5. Job 5: deadline 4, profit 7.
Answer: 47. Place Job3(20, d2) -> 2 and Job2(15, d2) -> 1. Job1 is dropped because slot 1 is full. Then place Job5(7, d4) -> 4 and Job4(5, d3) -> 3. Total = 20 + 15 + 7 + 5 = 47.
All three run on the same procedure: sort by profit, place each job in its latest free slot at or before its deadline, then add up the jobs that survived. The rule is easy; the bookkeeping is where marks are lost.
7. How exams test greedy scheduling, and the traps
The patterns are definitional MCQs, activity or room counts, feasibility orderings and profit NATs. GATE often uses NATs, where you cannot back-solve from options.
Three traps deserve special attention:
Filling the earliest free slot after sorting by profit. It may appear to work, but it wastes late capacity. Always take the latest legal slot.
Sorting activities by start time or duration instead of finish time.
Treating equality as overlap. A task ending at t may be followed by one starting at t.
Activity selection and unit-time job sequencing have the greedy-choice property. Problems such as 0/1 knapsack do not. Read Dynamic Programming Explained for that boundary, and revise Sorting Algorithms: Complexity, Stability, n log n Bound because every solution above begins with a sort.
8. The short version and where to practise next
For activity selection, choose earliest finish to maximise the count. For job sequencing, choose highest profit and take the latest legal slot.
The Job & Activity Selection practice module carries about 20 questions on this subtopic, the ones above included, each with a worked solution. For the whole Algorithms syllabus taught end to end, GATE Guidance by Sanchit Sir is the course that covers it.
Redo Q6, Q9 and Q10 from a blank page, without looking back at the traces. Greedy scheduling is scored on bookkeeping speed, and speed only comes from repetition.
