Description

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

[                     [  (1, 3),               (1, 6),  (2, 6),      =>       (8, 10),  (8, 10),              (15, 18)  (15, 18)            ]]

Challenge

O(n log n) time and O(1) extra space.

        题意：给定一个集合，里面有若干无序区间，要求将有重叠部分的区间合并。这个题目的示例给的不是很好，这个示例给人的感觉好像这些区间是有序的。有序和无序，用同样的方法做，结果可能不一样，比如我一开始理解成有序，报错如下：

Input

[(2,3),(4,5),(6,7),(8,9),(1,10)]

Output

[(2,3),(4,5),(6,7),(1,10)]

Expected

[(1,10)]

Hint

Review your code and make sure your algorithm is correct. Wrong answer usually caused by typos if your algorithm is correct.

Input test data (one parameter per line.)

        虽然它本来无序，但我们也可以人为地将它根据first值的大小进行排序，可以使用Collections类中的sort方法（查一下API）对List进行排序。排完之后，就可以对集合内的区间进行合并了。合并的方法与此题类似：   

        申请一个新的集合，再用一个循环，将排好序的区间两两比较，如果无需合并，则将前者加入新的集合，后者继续与后面的区间比较合并。代码如下：

1 public class Solution { 2     /** 3      * @param intervals: interval list. 4      * @return: A new interval list. 5      */ 6      //判断两区间是否相交 7     public List
        
          merge(List
         
           intervals) { 8         // write your code here 9         if(intervals.size()==0||intervals.size()==1)10            return intervals;11         List
          
           res=new ArrayList
           
            ();12         Collections.sort(intervals,new IntervalCompare());13         Interval last=intervals.get(0);14         for(int i=1;i
            
             {28         public int compare(Interval a,Interval b){29             return a.start-b.start;30         }31     }32 }
            
           
          
         
        

如有错误，欢迎批评指正~