import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MergeIntervals {
class Interval implements Comparable {
int start;
int end;
Interval(int s, int e) {
this.start = s;
this.end = e;
}
@Override
public int compareTo(Interval o) {
if(this.start o.start) return 1;
return 0;
}
}
List mergedIntervalList = new LinkedList();
public List mergeIntervals(Interval[] interval) {
Arrays.sort(interval);
for(int cur=1; cur interval[cur].end ? interval[prev].end : interval[cur].end);
interval[cur] = i;
}
else {
mergedIntervalList.add(interval[prev]);
}
}
mergedIntervalList.add(interval[interval.length-1]);
return mergedIntervalList;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MergeIntervals mi = new MergeIntervals();
Interval i1 = mi.new Interval(1,3);
Interval i2 = mi.new Interval(2,4);
Interval i3 = mi.new Interval(5,6);
Interval i4 = mi.new Interval(7,8);
Interval[] interval = {i3,i2,i4,i1};
List list = mi.mergeIntervals(interval);
System.out.println("Max non-overlapping intervals: " + list.size());
}
}