Activity Selection and Interval Scheduling | Algorithms I

Problem Statement

Given $n$ activities, each with a start time $s_i$ and finish time $f_i$ (with $s_i < f_i$ ), select the maximum-size subset of mutually compatible activities. Two activities $i$ and $j$ are compatible if their intervals do not overlap: $[s_i, f_i)$ and $[s_j, f_j)$ satisfy $f_i \le s_j$ or $f_j \le s_i$ . The half-open interval convention means an activity finishing at time $t$ permits another to start at time $t$ .

Greedy Strategy

Sort activities by finish time (ascending). Then:

Select the first activity (earliest finish).
Among activities that start at or after the finish time of the last selected activity, select the one with the earliest finish time.
Repeat until no more compatible activities remain.

sort activities by finish time
selected = {1}
k = 1
for i = 2 to n:
    if s[i] >= f[k]:
        selected = selected ∪ {i}
        k = i

Running time: $\Theta(n \log n)$ for sorting, then $\Theta(n)$ for the greedy scan.

Worked Example

Activity	Start	Finish
1	08:00	08:30
2	09:00	11:30
3	10:00	11:00
4	10:45	12:00

Sorted by finish time: $1(08:00\text{–}08:30), 3(10:00\text{–}11:00), 2(09:00\text{–}11:30), 4(10:45\text{–}12:00)$ .

Select 1 ( $k = 1$ ).
$i = 2$ : activity 3. $s_3 = 10:00 \ge f_1 = 8:30$ → select 3 ( $k = 3$ ).
$i = 3$ : activity 2. $s_2 = 9:00 < f_3 = 11:00$ → skip.
$i = 4$ : activity 4. $s_4 = 10:45 < f_3 = 11:00$ → skip.

Result: $\{1, 3\}$ . Optimal (size 2). Alternative optimal solutions: $\{1, 2\}$ , $\{1, 4\}$ — all achieve the same maximum cardinality.

Why Earliest Finish Time Works

The greedy choice is the activity with the earliest finish time. Intuition: this leaves the maximum remaining time for other activities, giving the greatest opportunity to schedule more.

Any other first choice would finish later and could only reduce (or at best leave unchanged) the amount of remaining time. There is never a reason to prefer a later-finishing activity.

Proof (Exchange Argument)

Let $A$ be an optimal solution. Let $k$ be the activity with the earliest finish time overall.

If $A$ contains $k$ , done.
If $A$ does not contain $k$ , let $j$ be the first activity in $A$ . Replace $j$ with $k$ . Since $f_k \le f_j$ , activity $k$ finishes no later than $j$ , so $k$ is compatible with all other activities in $A$ . The modified solution $A' = (A \setminus \{j\}) \cup \{k\}$ has the same size and is also optimal.

By induction, the greedy algorithm produces an optimal schedule.

DP Formulation (Unweighted)

The problem can also be solved with DP. Sort by finish time. Let $p(i)$ be the largest index $j < i$ with $f_j \le s_i$ . Then:

$\text{OPT}(i) = \max\big(\text{OPT}(i-1),\; 1 + \text{OPT}(p(i))\big)$

This is $\Theta(n^2)$ to compute all $p(i)$ values, or $\Theta(n \log n)$ with binary search on finish times. The greedy approach is simpler and equally optimal.

Weighted Variant

If each activity has a weight (value) and the goal is to maximise total weight rather than count, the greedy strategy fails. The DP formulation above remains correct with minor modification (using weight instead of 1), and no greedy shortcut exists. This is the weight-independent vs. weight-dependent distinction.

Discussion: Incorrect Heuristics

Shortest activity first: can select a short activity that blocks two longer, mutually compatible ones.
Earliest start time first: a very long activity starting early blocks everything else.
Fewest overlaps first: a counterexample exists where the activity with fewest overlaps still prevents a better combination.

Only earliest finish time greedily guarantees optimality for the unweighted case.

Summary

Property	Value
Problem	Maximise number of non-overlapping intervals
Greedy rule	Earliest finish time first
Time	$\Theta(n \log n)$ (sort) + $\Theta(n)$ (select)
Proof	Exchange argument
Weighted variant	Requires DP; greedy fails
Alternative heuristics	Shortest first, earliest start, fewest overlaps — all incorrect