4.2.1 The greedy method; activity selection

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Karatsuba recurrence? from Lesson 4.1.2
Quicksort worst case? from Lesson 3.2.2
Θ(n log n) comes from sorting which way? from Lesson 3.3.1

1 · The Hook

🎣

One lecture hall, many requested talks, each with a start and finish time. Which talks should you schedule to fit as many as possible? Try "shortest first" or "earliest start" and you can lose. "Finishes earliest" is always optimal. That is the greedy method: take the best-looking choice now, and prove it never hurts.

2 · Predict First

🤔

Talks (start, finish): P (1, 3), Q (2, 5), R (4, 6), S (6, 7), T (5, 9), U (8, 10), V (9, 11). Repeatedly pick the talk that finishes first among those that start after the last chosen one ends. Which talks do you get?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

P (ends 3) → R (starts 4, ends 6) → S (starts 6, ends 7) → U (starts 8, ends 10) → V starts 9 < 10, skip. P, R, S, U: 4 talks.

The greedy method

Build the solution step by step; at each step take the choice that looks best now and never undo it. It works when the problem has:

Greedy-choice property: some optimal solution starts with the greedy choice.
Optimal substructure: after making it, the rest is a smaller instance of the same problem.

Proofs usually use an exchange argument: take any optimal solution and swap its first choice for the greedy one without making it worse.

Activity selection

Given n activities with start sᵢ and finish fᵢ, choose a maximum set of mutually compatible activities (no overlaps; one may start exactly when another finishes).

Sort by finish time: Θ(n log n).
Take the first; then take each activity whose start ≥ finish of the last taken: Θ(n).

Why earliest finish works: the activity that finishes first leaves the most room; any optimal schedule can swap its first activity for it.

Rules that fail:

Shortest duration: (1, 5), (4, 7), (6, 10): shortest (4, 7) blocks both others; optimal picks 2.
Earliest start: a long activity starting first can block many.
Fewest conflicts: also fails on some inputs.

Example (11 activities)

Act	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	A11
s	1	3	0	5	3	5	6	8	8	2	12
f	4	5	6	7	9	9	10	11	12	14	16

Greedy picks A1, A4, A8, A11 (4 activities).

4 · Visual

time:  0    2    4    6    8    10   12   14   16
A1      [---]
A4                [-]
A8                      [--]
A11                              [----]
others overlap one of these: earliest finish leaves the most room each time

5 · Worked Examples

Example 1 Easy

Activities (1, 2), (2, 3), (3, 4), (1, 4). Maximum compatible set size?

Solution

(1, 2), (2, 3), (3, 4): 3.

Example 2 Medium

Show that "shortest activity first" can fail.

Solution

(1, 5), (4, 7), (6, 10): shortest is (4, 7), which overlaps both others → 1 activity; optimal (1, 5), (6, 10) → 2.

Example 3 GATE

Time complexity of greedy activity selection on n activities given in arbitrary order?

Solution

Sorting dominates: Θ(n log n) (Θ(n) if already sorted by finish time).

6 · GATE Traps

⚠️

Sort by finish time, not start time or length.
Compatibility allows start = previous finish.
A greedy algorithm needs a proof; an appealing rule can be wrong.
Activity selection maximises the number of activities, not total time used.

7 · Memory Hook

🧠

"Finish first, fit the most."

8 · Connect the Dots

Activity selection showed the greedy pattern and its proof. Next: two more greedy classics, the fractional knapsack (greedy by value per kilogram) and job sequencing with deadlines.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markActivity count

Activities (s, f): (1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16). Maximum number of compatible activities?

Numerical answer: ________

Q2MCQ1 markGreedy rule

Which rule always gives a maximum set of compatible activities?

(A) Earliest finish time first
(B) Shortest duration first
(C) Latest start time first, scanned from the left
(D) Earliest start time first

Q3NAT2 marksTrace

Talks P (1, 3), Q (2, 5), R (4, 6), S (6, 7), T (5, 9), U (8, 10), V (9, 11). How many does greedy activity selection choose?

Numerical answer: ________

Q4MSQ2 marksGreedy properties

For a greedy algorithm to be correct, which properties are typically shown?

(A) Overlapping subproblems
(B) Optimal substructure
(C) Exchange argument as proof technique
(D) Greedy-choice property

Q5NAT1 markCompatible

Activities (0, 3), (3, 6), (6, 9), (2, 7), (8, 10). Maximum compatible set size?

Numerical answer: ________

10 · Rule Card

Greedy: locally best choice, never undone; needs greedy-choice property + optimal substructure; prove by exchange.
Activity selection: sort by finish; pick if start ≥ last finish; Θ(n log n).
Shortest-first, earliest-start, fewest-conflicts can fail.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

greedy methodgreedy-choice propertyoptimal substructureexchange argumentactivity selectionearliest finish time rule

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

T(n) = 3T(n/2) + n.
Θ(n²).
Merge sort or heapsort (comparison sorts are Ω(n log n)).