Merge Intervals Solution

• The solution for this problem is derived around following ideas -

Let the interval of A be [Sa, Ea] and that of B be [Sb, Eb]. Following are the exhaustive cases.

1. If interval A finishes before interval B starts {Ea < Sb}, include both the intervals.
2. If interval A starts before interval B and ends after interval B { Sa < Sb, Ea > Eb}, include only interval A.
3. If interval B starts before interval A finishes {Sb<Ea}, include [Sa, Eb]

First, we have to sort the intervals according to their start times for this.

Code -

``````class Solution {

class IntervalComparator implements Comparator<Interval>
{
public int compare(Interval a, Interval b)
{
if(a.start!=b.start)
return a.start-b.start;
else
return a.end-b.end;

}
}
public List<Interval> merge(List<Interval> intervals) {
if(intervals==null || intervals.size()<2)
return intervals;
else
{
Collections.sort(intervals, new IntervalComparator());
List<Interval> returnList = new ArrayList<Interval>();
Interval current = intervals.get(0);
Interval next = null;
for(int i=1;i<intervals.size();i++)
{
next = intervals.get(i);
if(next.start > current.end)
{
current = next;
}
else
{
current.end = Math.max(current.end, next.end);
}
}