title: Algorithm to find the maximum sum in a sequence of overlapping intervals
body: <p>The problem I am trying to solve has a list of intervals on the number line, each with a pre-defined score. I need to return the maximum possible total score. </p>
  
  <p>The catch is that the intervals overlap, and of the overlapping intervals I can use only one. Here is an example. </p>
  
  <pre><code>Intervals   - Score  
     0- 5     -  15  
     4- 9     -  18  
    10-15     -  12  
     8-21     -  19  
    25-30     -  25    
  </code></pre>
  
  <p>Here, the intervals 0-5, 4-9 and 8-21 overlap.<br>
  The intervals 10-15 and 8-21 also overlap.<br>
  The maximum sum would be 55 (18+12+25). </p>
  
  <p>It is important to note here that we select the interval 4-9 of the first batch of overlapping intervals even though it does not have the highest score of the three. </p>
  
  <p>This is because selecting the interval 8-21 would prevent us from using the interval 10-15 later on, thereby reducing the overall sum (In that case, the overall sum would be 19+25=44). </p>
  
  <p>I am looking for an O(nlogn) or O(n) solution to this problem. I think dynamic programming can be used, but I may be wrong. Could someone suggest a solution/algorithm(s) that could do the trick here? </p>
  
  <p>Edit: The intervals are in no particular order. </p>