合并区间（LintCode） .

合并区间

给出若干闭合区间，合并所有重叠的部分。

样例

给出的区间列表 => 合并后的区间列表：

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

挑战

O(n log n) 的时间和 O(1) 的额外空间。

思路是清晰的，代码是混乱的。先用Collection.sort()方法对List排序。当然也可以先toArray()然后用Arrays.sort()排序。但是都需要写一个实现Comparator接口的内部类。

 1 /**
 2  * Definition of Interval:
 3  * public class Interval {
 4  *     int start, end;
 5  *     Interval(int start, int end) {
 6  *         this.start = start;
 7  *         this.end = end;
 8  *     }
 9  */
10 
11 class Solution {
12     /**
13      * @param intervals: Sorted interval list.
14      * @return: A new sorted interval list.
15      */
16      
17     public class IntervalCmp implements Comparator<Interval> {
18         public int compare(Interval i1, Interval i2) {
19             if (i1.start < i2.start) return -1;
20             if (i1.start == i2.start && i1.end <= i2.end) return -1;
21             return 1;
22         }
23      }
24     public List<Interval> merge(List<Interval> intervals) {
25         if(intervals.size() == 1)return intervals;
26         List<Interval> list = new ArrayList<Interval>();
27         int max1 = -1;
28         int min1 = 99999999;
29         int max = -1;
30         int min = 99999999;
31         
32         //借助Collections。sort()排序，百度了一下JDK7不加上这句的话可能会报错
33         System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
34         Collections.sort(intervals, new IntervalCmp());
35         
36         for(int i = 0;i<intervals.size();i++) {
37             Interval x = intervals.get(i);
38             if(x.start > max1 || x.end < min1) {
39                 min = x.start;
40                 max = x.end;
41                 for(int j = i+1;j<intervals.size();j++) {
42                     Interval y = intervals.get(j);
43                     if(y.end >= min && y.start <= max) {
44                         if(max < y.end) {
45                             max = y.end;
46                         }
47                         if(min > y.start) {
48                             min = y.start;
49                         }
50                     }
51                 }
52                 x.end = max;
53                 x.start = min;
54                 if(max1 < max) max1 = max;
55                 if(min1 > min) min1 = min;
56                 list.add(x);
57             }
58         }
59         return list;
60     }
61 
62 }

View Code

在说一下比较器抛

java.lang.IllegalArgumentException: Comparison method violates its general contract

这个异常，JDK7以后用比较器在两个元素相等的情况下需要返回0。可参考：这里