title: How do I prove designed Min Interval Algorithm?
body: <p>I am trying to learn how to prove the correctness and optimality of algorithms. For this I am trying to do it for the problem:</p>
  <p>Input is interval list ([l1,r1],[l2,r2],...,[ln,rn])</p>
  <p>Find the minimal interval coverage that is the coverage with the least amount of intervals containing all intervals from the interval list.</p>
  <p>For ([1,4],[2,7],[10,11]) it would be ([1,7],[10,11])</p>
  <pre><code>sort(X)  //sort X by increasing interval start l
  l' &lt;- left(x0)
  r' &lt;- right(x0)
  remove(x0,X)  //remove x0 from interval list X
  for x in X:
   l&lt;- left(x)
   r&lt;- right(x)
   if r&gt;r' and l&lt;=r'+1:
    r'&lt;-r
   if l&gt;r':
    expandedX = [l',r']
    Result.add(expandedX)
    l'=left(x)
    r'=right(x)
  </code></pre>
  <p>Runtime in O(nlogn+n)</p>
  <p>Now I really don't know how to prove it.</p>
  <p>How do I get to an systematic approach resulting in a valid good proof?</p>
  <p>My attempt:</p>
  <p>Let Y be the interval coverage produced by the algorithm and let Y' be the optimal interval coverage.</p>
  <p>Suppose Y is not optimal.</p>
  <p>Hence |Y'|&lt; |Y|</p>
  <p>This implies that there exists an y in Y such that y not in Y' and there exists y' such that y is a subset of y'</p>
  <p>This implies that there exists y'' in Y such that left(y'')&lt;=right(y)</p>
  <p>Is this a valid start?</p>