Merge Intervals

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 1:

1. 先使用Comparator 的匿名类对intervels进行排序。

2. 把Intervals遍历一次，依次一个一个merge到第1个interval。 把第1个interval设置为last(最后一个加到结果集里）

有2种情况：

  （1) cur在last的后面。把last加到结果集，将cur加到结果集中。

    (2）cur与last有重合部分，把它们合并，合并之后的区间作为新的last.

所有的都扫完后，把last加到结果集中即可。

 

注意：因为现在Leetcode所有入参都搞成了List,所以遍历时最好使用Iterator，这样无论对于Linkedlist,还是arraylist，性能都是一样的，否则使用get(i)对于LinkedList会相当的缓慢，就不是O(1)的时间了。

复杂度：排序是NlogN, 而merge本身是N。所以总体时间复杂度是NlogN

1 /** 2  * Definition for an interval. 3  * public class Interval { 4  *     int start; 5  *     int end; 6  *     Interval() { start = 0; end = 0; } 7  *     Interval(int s, int e) { start = s; end = e; } 8  * } 9  */10 public class Solution {11     public List
      
        merge(List
       
         intervals) {12         List
        
          ret = new ArrayList
         
          ();13         if (intervals == null || intervals.size() == 0) {14             return ret;15         }16         17         Collections.sort(intervals, new Comparator
          
           () {18             public int compare(Interval o1, Interval o2) {19                 // sort the intervals by the start.20                 return o1.start - o2.start;21             }22         });23         24         // 作为最后一个插入的区间25         Interval last = intervals.get(0);26         27         // 这里要考虑性能。使用iterator的话，对linkedlist会更快.        28         Iterator
           
             itor = intervals.iterator();29 while (itor.hasNext()) {30 Interval cur = itor.next();31 // cur 在last的右边32 if (cur.start > last.end) {33 // 将cur作为新的last.34 ret.add(last);35 last = cur;36 // cur与last有重合的部分，合并之 37 } else {38 int s = last.start;39 int e = Math.max(last.end, cur.end);40 last = new Interval(s, e);41 }42 }43 44 // 把最后一个区间加上45 ret.add(last);46 47 return ret;48 }49 }
           
          
         
        
       
      

 

 

REF: