1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.