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.

The catch is that the intervals overlap, and of the overlapping intervals I can use only one. Here is an example. 

Intervals   - Score  
   0- 5     -  15  
   4- 9     -  18  
  10-15     -  12  
   8-21     -  19  
  25-30     -  25

Here, the intervals 0-5, 4-9 and 8-21 overlap.
The intervals 10-15 and 8-21 also overlap.
The maximum sum would be 55 (18+12+25).

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.

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).

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?

Edit: The intervals are in no particular order.

algorithm sum max intervals
Edit
Report