Prove this greedy algorithm is optimal So the question is: Consider the following different greedy algorithm for the Interval Scheduling algorithm:
DifferentGreedySchedule
- Initialize R to contain all intervals - While R is not empty
- Choose an interval (S(i),F(i)) from R that has the largest value of S(i) 
- Delete all intervals in R that overlaps with (S (i), F (i))
I know exactly that this algorithm will produce an optimal solution but I don't what is the best way to prove it? Or how exactly should I use the Greedy stays ahead?
Thanks a lot for your help!
 A: You can show correctness of this algorithm via induction on the number of intervals in the optimal solution.
Assume that your greedy strategy works for $n$ intervals in the optimal solution. Let $R_\mathrm{OPT}$ denote an optimal set of $n + 1$ intervals and $R_\mathrm{DGS}$ the set of intervals produced by your greedy strategy. Let $i_\mathrm{OPT}$ be the last interval (i.e. with largest starting time $S(i_\mathrm{OPT})$) of $R_\mathrm{OPT}$ and $i_\mathrm{DGS}$ the last interval of $R_\mathrm{DGS}$. By the choice of $i_\mathrm{DGS}$ as the interval with largest starting time $S(i_\mathrm{DGS})$, we can replace interval $i_\mathrm{OPT}$ by interval $i_\mathrm{DGS}$ in $R_\mathrm{OPT}$ without causing any interval intersections.
Let $R'$ denote the set of all intervals $i$ with finishing time $F(i) \leq S(i_\mathrm{OPT}) \leq S(i_\mathrm{DGS})$. Obviously, $R_\mathrm{OPT} \setminus \{i_\mathrm{OPT}\}$ must be optimal for this set of intervals and has $n$ intervals. Thus, we can apply the assumption, showing that $R_\mathrm{DGS} \setminus \{i_\mathrm{DGS}\}$ must be optimal for $R'$ as well. But then $R_\mathrm{DGS}$ and $R_\mathrm{OPT}$ must both be optimal for $R$.
