3.6 Merge Interval

Description

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].

Method

since we need to find the whether two intervals has overlap, if have, we need to merge them. So we can sort the intervals by start and then we just need to compare the start of one interval with the start of the previous intervals.

we use two pointers to do the compare operations. then we can just jump to the next start index;

Time and Space Complexity

(nlogn + n)

Code

public class Solution {

public List<Interval> merge(List<Interval> intervals) {
       List<Interval> ans = new ArrayList<Interval>();
       if (intervals == null || intervals.size() == 0){
           return ans;
       }
       Collections.sort(intervals, new Comparator<Interval>(){
                public int compare(Interval a, Interval b){
                       if (a.start == b.start){
                           return a.end - b.end;
                       } else {
                          return a.start - b.start; 
                       }
                }
       });
       Interval pre = null;

       for (Interval cur : intervals){
              if (pre == null || cur.start > pre.end){
                  ans.add(cur);
                  pre = cur;
              } else if (cur.end > pre.end) {
                 pre.end = cur.end;
              }
       }
       return ans;

}

}