56. Merge Intervals Leetcode Java

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:

Sort the list first. Build a new comparator for comparing intervals. The comparator will compare start first, then compare the end.

Use a variable "end" initiated with 0 to track the index of last merged interval. When we transverse the list, check if the current interval has intersection with list[end], if yes, merge them and assign it back to list[end], if no, put the current interval to "end+1" position and increment the "end"

Time complexity: O(nlogn) 

 public List<Interval> merge(List<Interval> intervals) {  
     if(intervals==null || intervals.size()<=1) return intervals;  
   Comparator<Interval> intervalComparator=new Comparator<Interval>(){  
     @ Override  
     public int compare(Interval i1, Interval i2){  
       if(i1.start==i2.start) return i1.end-i2.end;  
       else return i1.start-i2.start;  
     }  
   };  
   Collections.sort(intervals,intervalComparator);  
   int end=0;  
   for(int i=1;i<intervals.size();i++){  
     if(intervals.get(i).start<=intervals.get(end).end){  
       intervals.set(end, new Interval(intervals.get(end).start,Math.max(intervals.get(end).end,intervals.get(i).end)));  
     }  
     else {  
       end++;  
       intervals.set(end,intervals.get(i));  
     }  
   }  
   return intervals.subList(0,end+1);  
   }