Activity Selection Problem and a “Last-Start” Greedy Strategy

The activity selection problem is a classic optimization problem on intervals. Each activity $i$ has a start time $s_i$ and finish time $f_i$ with $s_i < f_i$. Two activities are compatible if they do not overlap, i.e., for activities $i$ and $j$ with $f_i \le s_j$ (equivalently, one finishes before the other starts).

A standard greedy strategy chooses the activity with the earliest finish time among those that are compatible with what you have already chosen. The variant you asked about uses a “reverse” viewpoint:

Instead of selecting the first compatible activity to finish, select the last activity to start that is compatible with all previously selected activities.

This “last-start compatible” rule is also a greedy algorithm, and it can be proven optimal by an exchange argument using interval ordering properties.

Key terms: compatible activities , greedy-choice property , exchange argument , optimal substructure.

---

Formal problem statement

Let the set of activities be $A=\{1,2,\dots,n\}$. Activity $i$ is the closed-open interval $[s_i, f_i)$ (any consistent overlap convention works). We want a maximum-size subset $S \subseteq A$ such that for any two activities $i,j \in S$, they do not overlap: if $i$ precedes $j$ then $f_i \le s_j$.

A greedy algorithm repeatedly extends a partial solution by choosing a single “best” activity according to some local rule, without reconsidering earlier choices.

In the last-start compatible strategy, we proceed like this:

1. Maintain the already selected set (initially empty).
2. Among activities that are compatible with all already-selected ones, choose the activity with the largest start time.
3. Add it to the set.
4. Repeat on the remaining activities that are compatible with the augmented set.

To make implementation and reasoning clean, we typically order activities by finish time (or by start time depending on the proof). For the last-start strategy, ordering by start time is intuitive, but the proof can be framed using finish times to preserve the non-overlap structure.

Key terms: interval ordering , selection subset , feasible solution , maximal cardinality.

Why this is a greedy algorithm

By construction, at each step the algorithm makes a single local decision: it chooses the compatible activity with the largest start time and never revisits that choice.

Formally, let $S_k$ be the set selected after $k$ iterations. The $(k+1)$-st iteration picks an activity $a_{k+1}$ that:

• is compatible with $S_k$, and
• maximizes $s_a$ among such compatible candidates.

This is the hallmark of the greedy paradigm: a local optimization criterion that determines the next element of the solution.

Key terms: greedy choice , partial solution , iteration invariant.

Correctness proof (optimality via exchange argument)

We prove that the “last-start compatible” greedy strategy yields an optimal solution (maximum number of non-overlapping activities).

Setup and ordering

Let the activities be distinct or ties handled consistently. Sort activities by start times decreasing (so “last to start” means highest start time).

At any stage, the already selected activities form a feasible schedule. Let the “current boundary” be the earliest start time among activities already selected (because we are building backward: we pick an activity that must end before the boundary starts, so it can fit without overlapping what is already selected).

Define a subproblem: given a boundary time $T$, consider only activities that finish at or before $T$:

$$A(T) = \{ i \mid f_i \le T \}.$$

Then the goal is to select the maximum number of pairwise non-overlapping activities from $A(T)$.

The greedy rule chooses, from $A(T)$, the activity $g(T)$ with the largest start time:

$$g(T) \in \arg\max_{i \in A(T)} s_i.$$

After choosing $g(T)$, we update the boundary to $s_{g(T)}$, because any additional activity must end before the start of the newly chosen one.

Thus, the algorithm is recursively:

• pick $g(T)$,
• then solve the subproblem with boundary $T' = s_{g(T)}$.

Lemma (greedy-choice property)

Lemma: There exists an optimal solution for subproblem $A(T)$ that includes the greedy choice $g(T)$.

Proof (exchange argument): Let $O$ be an optimal solution for $A(T)$. If $g(T) \in O$, we are done.

Otherwise, $g(T) \notin O$. Consider the activity $o \in O$ that is the first activity in $O$ (in the backward sense) that conflicts with $g(T)$ or, equivalently, the activity in $O$ with the largest start time among those that are compatible to the same extent. A more direct interval argument works:

• Since both $g(T)$ and activities in $O$ are feasible within $A(T)$, every activity in $O$ must lie in time positions that do not overlap each other, and they all finish by $T$.
• Let $j$ be the activity in $O$ with the largest start time among those in $O$. Because $O$ is a set of non-overlapping intervals within $(-\infty, T]$, these intervals have an induced order.
• Compare $g(T)$ with $j$. By definition of $g(T)$, we have $s_{g(T)} \ge s_j$.
• Replace $j$ with $g(T)$ in $O$ to form a new set: $$O' = (O \setminus \{j\}) \cup \{g(T)\}.$$ We claim $O'$ is feasible and has the same cardinality.

Feasibility reasoning: because $g(T)$ has the latest start among all activities that finish by $T$, and because $j$ was the latest-start interval in $O$, swapping $g(T)$ in cannot create overlap with activities earlier in the schedule (they all end $\le$ the start boundary imposed by the later activity), and $g(T)$ also finishes by $T$ so it does not overlap the later-than-$T$ region (none exists). Therefore, all non-overlap constraints remain satisfied.

Thus, $O'$ is feasible, has $|O'|=|O|$, and includes $g(T)$. Hence, there exists an optimal solution that contains the greedy choice. 

Theorem (global optimality)

The greedy algorithm is optimal: the solution it outputs has maximum possible size.

Proof (induction on the number of activities / subproblem boundary): We prove by induction on the “size” of the subproblem $A(T)$ (e.g., number of candidate activities).

• Base case: If $A(T)$ is empty or contains only one activity, the greedy algorithm is trivially optimal.
• Inductive step: Assume the algorithm is optimal for all smaller subproblems (with earlier boundaries). Consider subproblem $A(T)$.
  • By the Lemma, there exists an optimal solution $O$ that includes the greedy activity $g(T)$.
  • After selecting $g(T)$, the remaining activities must all lie in the subproblem with boundary $T' = s_{g(T)}$.
  • The greedy algorithm then solves this subproblem optimally by the induction hypothesis.
  • Therefore, combining $g(T)$ with the optimal remaining solution produces an optimal solution for $A(T)$.

Hence, by induction, the greedy algorithm yields a globally optimal maximum-size feasible set. 

Key terms: subproblem boundary , induction on subproblems , feasibility preserved.