How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm?

Question

I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem.

On the second page of Cornell's Greedy Stays Ahead handout, I don't understand a few things:

1. All of the proofs make the base case seem so trivial (when r=1). I don't understand the context behind the base case - perhaps in more easy to understand terms.
2. Are we essentially proving that the number of maximum activities in A cannot exceed the number of activities in O?

In short, are we saying that if A is not optimal, then there would be at least 1 more activity in the optimal solution, O, which would contradict our assumption that O is optimal and that A is the set of requests made by the greedy algorithm? Because we don't say that A is optimal. But we know that it's the set of requests selected by the greedy algorithm. So, if it doesn't include the same number of requests than O, then we know that it couldn't have been selected by the greedy algorithm?

Answer 1

What we are saying is that if A is not optimal, then the number of jobs in A (let it be k) should be less than the number of jobs in O ( let it be m).

That means, there must be (k+1)-th job in O, while the k-th job is the last job in A.

Since (k+1)-th job in O must start after k-th job in O, and we know that any i-th job in A finishes earlier than i-th job in O, that means k-th job in A finishes earler than k-th job in O.

That means, the (k+1)-th job in O can be added to A, which contradicts that A only has k jobs. Hence, A must be optimal and it must have m items.