Maximum sum of the range non-overlapping intervals in a list of Intervals
algorithm, dynamic-programming, greedy, intervals
Solution
This is a standard interval scheduling problem. It can be solved by using dynamic programming.
Algorithm Let there be `n` intervals. `sum[i]` stores maximum sum of interval up to interval `i` in sorted interval array. The algorithm is as follows
Sort the intervals in order of their end timings.
sum[0] = 0
For interval i from 1 to n in sorted array
j = interval in 1 to i-1 whose endtime is less than beginning time of interval i.
If j exist, then sum[i] = max(sum[j]+duration[i],sum[i-1])
else sum[i] = max(duration[i],sum[i-1])
The iteration goes for `n` steps and in each step, `j` can be found using binary search, i.e. in `log n` time. Hence algorithm takes `O(n log n)` time.
Problem
Someone asked me this question: You are given a list of intervals. You have to design an algorithm to find the sequence of non-overlapping intervals so that the sum of the range of intervals is 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 is maximized when three intervals ``` [“06:00”, “08:30”], [“09:00”, “11:30”], [“12:00”, “14:00”], ``` are chosen. Therefore, the answer is 420 (minutes).