合并区间（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接口的内部类。

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */

class Solution {
    /**
     * @param intervals: Sorted interval list.
     * @return: A new sorted interval list.
     */
     
    public class IntervalCmp implements Comparator<Interval> {
        public int compare(Interval i1, Interval i2) {
            if (i1.start < i2.start) return -1;
            if (i1.start == i2.start && i1.end <= i2.end) return -1;
            return 1;
        }
     }
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size() == 1)return intervals;
        List<Interval> list = new ArrayList<Interval>();
        int max1 = -1;
        int min1 = 99999999;
        int max = -1;
        int min = 99999999;
        
        //借助Collections。sort()排序，百度了一下JDK7不加上这句的话可能会报错
        System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
        Collections.sort(intervals, new IntervalCmp());
        
        for(int i = 0;i<intervals.size();i++) {
            Interval x = intervals.get(i);
            if(x.start > max1 || x.end < min1) {
                min = x.start;
                max = x.end;
                for(int j = i+1;j<intervals.size();j++) {
                    Interval y = intervals.get(j);
                    if(y.end >= min && y.start <= max) {
                        if(max < y.end) {
                            max = y.end;
                        }
                        if(min > y.start) {
                            min = y.start;
                        }
                    }
                }
                x.end = max;
                x.start = min;
                if(max1 < max) max1 = max;
                if(min1 > min) min1 = min;
                list.add(x);
            }
        }
        return list;
    }

}

在说一下比较器抛

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

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