title: Find the smallest set of overlapping jobs
body: <p>A friend gave me a puzzle that he says can be solved in better than O(n^3) time.</p>
  
  <p>Given a set of n jobs that each have a set start time and end time (overlaps are very possible), find the smallest subset that for every job either includes that job or includes a job that has overlap with that job.</p>
  
  <p>I'm pretty sure that the optimal solution is to pick the job with the most unmarked overlap, add it to the solution set, then mark it, and its overlap. And repeat until all jobs are marked.<br>
  Figuring out which job has the most unmarked overlappers is a simple adjacency matrix (O(n^2)), and this has to be redone every time a job is selected, in order to update the marks, making it O(n^3).</p>
  
  <p>Is there a better solution?</p>