title: Algorithm to find maximum coverage of non-overlapping sequences. (I.e., the Weighted Interval Scheduling Prob.)
body: <p>I have a question that is very similar to <a href="https://stackoverflow.com/questions/4593583/algorithm-to-find-longest-non-overlapping-sequences">algorithm to find longest non-overlapping sequences</a>.</p>
  
  <p>The only difference to the linked question is that instead of finding the set of non-overlapping tuples that represent the <strong>longest sequence</strong>, I need to find the set of non-overlapping tuples that represent the <strong>maximum coverage</strong>, by which I mean the <em>sum of the tuple lengths</em> is maximum (a <em>tuple length</em> being <code>last - first + 1</code> given the definition of <em>tuple</em> in the next sentence).</p>
  
  <p>I represent my tuples differently than the linked problem.  Instead of <code>(starting index, length)</code>, I represent my tuples as <code>(first, last)</code>; for example, the tuple <code>(3,7)</code> represents the set of numbers <code>[3, 4, 5, 6, 7]</code>.  (A tuple <em>overlaps</em> another tuple even if the end-points match; i.e., <code>(2,6)</code> and <code>(6,8)</code> <em>overlap</em> and therefore cannot both appear in the solution.)</p>
  
  <p>As an example, consider the following set of tuples, sorted by <code>first</code>:</p>
  
  <p><code>[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]</code></p>
  
  <p>The maximal set here would be <code>[(0,100), (110,190), (191,200)]</code> with a coverage of <code>101 + 81 + 10 = 192</code>.  (Note that the tuples in this solution are <em>non-overlapping</em>.)</p>
  
  <p>What is an example of the least complex algorithm to solve this, and what is the complexity of that algorithm?  (It would be just great if this could be solved in <code>O(N)</code>, but I don't know at the moment if it can be.)</p>
  
  <p><strong>ADDENDUM:</strong> In retrospect, it turns out that the question I am asking here is equivalent to the <a href="http://farazdagi.com/blog/2013/weighted-interval-scheduling/" rel="nofollow noreferrer"><strong>weighted interval scheduling problem</strong></a>.  This is a special case of the <a href="https://en.wikipedia.org/wiki/Interval_scheduling" rel="nofollow noreferrer">interval scheduling problem</a>.</p>
  
  <p>@j_random_hacker's answer, below, is, in fact, the known solution to the weighted interval scheduling problem, with a complexity in time of <code>O(N log(N))</code>.</p>