title: Dynamic Programming Solution for Activity-selection
body: <p>In <code>16.1 An activity-selection problem</code> of <code>Introduction to Algorithm</code>, the dynamic programming solution for this problem was given as</p>
  
  <blockquote>
    <p>c[i, j] = 0 if S(i, j) is empty</p>
    
    <p>c[i, j] = max { c[i, k] + c[k, j] + 1 } if S(i, j) is not empty</p>
  </blockquote>
  
  <p>where <code>S(i, j)</code> denotes the set of activities that start after activity <code>a(i)</code> finishes and that finish before activity <code>a(j)</code> starts, and <code>c[i, j]</code> denotes the size of an optimal solution for the set <code>S(i, j)</code></p>
  
  <p>However, I am thinking of another simpler solution</p>
  
  <pre><code>c[i] = max { c[i - 1], c[f(i)] + 1 }
  </code></pre>
  
  <p>where <code>f(i)</code> gives the activity that is compatible with <code>a(i)</code> and has the max <strong>finish time and finishes before <code>a(i)</code> starts.</strong></p>
  
  <p>Will this work? If yes, why the author provides this complex solution. If not, what am I missing?</p>