title: Implementing Activity Selection Prob using Dynamic Programming
body: <p>How to implement Activity Selection Problem using Dynamic Programming (CLRS Exercise 16.1-1). I've implemented it using Greedy Method, which runs in linear time (assuming array is already sorted with finish time). </p>
  
  <p>I know it poses Optimal substructure.</p>
  
  <p>Let <code>$S_{ij}$</code> the set of activities that start after activity <code>$a_i$</code> finishes and
  that finish before activity <code>$a_j$</code> starts. If we denote the size of an optimal solution for the set <code>$S_{ij}$ by $c[i j]$</code> , then we would have the recurrence</p>
  
  <pre><code>$c[i j]  = c[i k] + c[k j] + 1$
  </code></pre>