algorithm - Maximum sum of the range non-overlapping intervals in a list of Intervals -

someone asked me question:
given list of intervals. have design algorithm find sequence of non-overlapping intervals sum of range of intervals maximum.

for example:
if given intervals are:

["06:00","08:30"], ["09:00","11:00"], ["08:00","09:00"], ["09:00","11:30"], ["10:30","14:00"], ["12:00","14:00"] 

range maximized when 3 intervals

[“06:00”, “08:30”], [“09:00”, “11:30”], [“12:00”, “14:00”], 

are chosen.

therefore, answer 420 (minutes).

this standard interval scheduling problem.
can solved using dynamic programming.

algorithm
let there n intervals. sum[i] stores maximum sum of interval interval i in sorted interval array. algorithm follows

sort intervals in order of end timings. sum[0] = 0 interval 1 n in sorted array     j = interval in 1 i-1 endtime less beginning time of interval i.     if j exist, sum[i] = max(sum[j]+duration[i],sum[i-1])     else sum[i] = max(duration[i],sum[i-1]) 

the iteration goes n steps , in each step, j can found using binary search, i.e. in log n time. hence algorithm takes o(n log n) time.