Maximum sum of intervals of non-overlapping intervals in the list of intervals

Question

Someone asked me this question:
You are given a list of intervals. You must develop an algorithm for finding a sequence of non-overlapping intervals so that the sum of the interval of intervals is maximum.

For instance:
If the specified intervals:

["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 maximum if three intervals

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

.

Therefore, the answer is 420 (minutes).

Answer 1

This is a standard interval planning task.
It can be solved using dynamic programming.

Algorithm
Let there be intervals n . sum[i] stores the maximum sum of the interval to interval i in an array of sorted intervals. 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]) 

Iteration goes for steps n , and at each step j can be found using binary search, i.e. in log n time. Therefore, the algorithm takes time O(n log n) .

Answer 2

 public int longestNonOverLappingTI(TimeInterval[] tis){ Arrays.sort(tis); int[] mt = new int[tis.length]; mt[0] = tis[0].getTime(); for(int j=1;j<tis.length;j++){ for(int i=0;i<j;i++){ int x = tis[j].overlaps(tis[i])?tis[j].getTime():mt[i] + tis[j].getTime(); mt[j] = Math.max(x,mt[j]); } } return getMax(mt); } public class TimeInterval implements Comparable <TimeInterval> { public int start; public int end; public TimeInterval(int start,int end){ this.start = start; this.end = end; } public boolean overlaps(TimeInterval that){ return !(that.end < this.start || this.end < that.start); } public int getTime(){ return end - start; } @Override public int compareTo(TimeInterval timeInterval) { if(this.end < timeInterval.end) return -1; else if( this.end > timeInterval.end) return 1; else{ //end timeIntervals are same if(this.start < timeInterval.start) return -1; else if(this.start > timeInterval.start) return 1; else return 0; } } } 

Here is the working code. This is mostly done in O (n ^ 2) due to two loops. But since Shashvat said there are ways to make it work in O (n lg n)