Greedy strategy & activity selection — COMP 372

What makes an algorithm greedy

A greedy algorithm makes the choice that looks best right now and never reconsiders it. It commits to a locally optimal choice before solving any subproblem, then recurses on the one subproblem that remains. This is the opposite of dynamic programming, which solves subproblems first and only then chooses. Greedy is therefore top-down and DP is bottom-up; greedy considers exactly one choice per step where DP considers all of them.

Greedy does not always work. When it does, the problem has two properties:

Greedy-choice property — a globally optimal solution can be built by making locally optimal (greedy) choices. The greedy choice may depend on choices made so far, but not on the solutions to future subproblems.
Optimal substructure — an optimal solution to the problem contains optimal solutions to its subproblems. (DP needs this too; greedy uses it after assuming the greedy choice is already made.)

The activity-selection problem

You are given $n$ activities, each with a start time $s_{i}$ and a finish time $f_{i}$ (the activity occupies the half-open interval $[s_{i}, f_{i})$ ). Two activities are compatible if their intervals do not overlap. The goal is to select a maximum-size set of mutually compatible activities — think of scheduling the most events possible in one lecture hall.

The greedy choice: sort the activities by finish time, then always take the next activity whose start time is at or after the finish time of the last one you took. Taking the earliest-finishing compatible activity leaves the resource free as soon as possible, maximizing room for the rest.

Worked example. With 11 activities sorted by finish time (CLRS Fig. 15.1):

$i s_{i} f_{i} 11423530645753965976108811981210214111216$

Take $a_{1}$ (finishes at 4). The next compatible one is $a_{4}$ (starts at $5 \geq 4$ , finishes at 7). Then $a_{8}$ (starts at $8 \geq 7$ , finishes at 11). Then $a_{11}$ (starts at $12 \geq 11$ ). Result: ${a_{1}, a_{4}, a_{8}, a_{11}}$ — four activities, which is optimal.

Why earliest-finish is safe (Theorem 15.1)

The correctness rests on an exchange argument, the canonical proof for the greedy-choice property. Let $a_{m}$ be the earliest-finishing activity in a subproblem, and let $A$ be any maximum-size compatible set for that subproblem. Let $a_{j}$ be the earliest-finishing activity in $A$ . If $a_{j} = a_{m}$ , we are done. Otherwise build $A^{'} = (A - {a_{j}}) \cup {a_{m}}$ . Because $f_{m} \leq f_{j}$ , swapping $a_{j}$ out for $a_{m}$ keeps every later activity compatible, so $A^{'}$ is still valid and $∣ A^{'} ∣ = ∣ A ∣$ . Thus a maximum-size solution containing the greedy choice exists. ∎

After the $O (n l g n)$ sort, the selection loop is $Θ (n)$ : each activity is examined once. Contrast this with the $Θ (n^{2})$ DP recurrence $c [i, j] = max_{k} {c [i, k] + c [k, j] + 1}$ that the greedy choice collapses into a single $O (1)$ choice per step.

The first six activities (already sorted by finish time) on one time line. Greedy takes a1, then the first activity that starts at or after 4.

Why the greedy key must be finish time — same instance, two sort orders.

Greedy commits before recursing; DP recurses before committing.