diff options
| -rw-r--r-- | assignment11.tex | 18 |
1 files changed, 17 insertions, 1 deletions
diff --git a/assignment11.tex b/assignment11.tex index eec7ccb..ac824df 100644 --- a/assignment11.tex +++ b/assignment11.tex @@ -103,7 +103,23 @@ \end{enumerate} - \item %todo + \item \begin{enumerate} + \item Start with the set of intervals $I=\emptyset$. While $S$ is non-empty: + \begin{enumerate}[ref=\roman*] + \item Extract the smallest $x_i$ from $S$. + \item Add $[x_i,x_i+1]$ to $I$. \label{11-5-a-choice} + \item Remove all $x_j$ with $x_j \in [x_i,x_i+1]$ from $S$. + \end{enumerate} + Return $I$. + + \item \begin{proof} + Suppose the algorithm was not correct. Then in step \ref{11-5-a-choice} we could have chosen a different interval containing $x_i$, all the $x_j$ from the next step \emph{and} at least one other $x_j'$. However, any other option for an interval would have a lower lower bound and a lower upper bound. Therefore, $x_j'<x_i$. However, since $x_i$ is minimal, this $x_j'$ cannot exist. Therefore, our choice of $[x_i,x_i+1]$ is optimal. + \end{proof} + + The greedy choice is to take the interval which contains $x_i$ and as many as possible other values. + + I don't get the question about the optimal substructure, it's a term I only know from dynamic programming which doesn't apply here. + \end{enumerate} \end{enumerate} |