Activity Selection - The Exchange

Proof: Let OPT be any optimal solution, and G be the greedy solution. Let $g_1$ be greedy's first choice (activity ending earliest). Let $o_1$ be OPT's first activity.

Case $1$: $o_1 = g_1$. No difference here; move to the next activity.

Case $2$: $o_1 \neq g_1$. Since $g_1$ ends earliest, $end(g_1) \leq end(o_1)$. Create OPT' by replacing $o_1$ with $g_1$ in OPT. Is OPT' valid? Yes! Since $g_1$ ends no later than $o_1$, it does not conflict with OPT's later activities (they started after P10 ended). OPT' has the same number of activities as OPT, so it is still optimal.