[LeetCode]Merge Intervals

Question

本题难度Hard。

排序+双指针

【复杂度】
时间 O(Nlog(N)) 空间 O(N)

【思路】
先按照每个元素的​​​start​​​从小到大进行排序。然后利用双指针法，设置区间​​(low,high)​​​，如果新的元素​​i​​​的​​start​​​要大于​​high​​​，说明​​(low,high)​​​没有overlap，就将​​(low,high)​​放入结果中，然后将双指针移动：

low=i.start;
high=i.end;

否则就进行合并。

【注意】

1、第30行别忘写了，循环中并没有让最后一个间隔加入到结果中

2、判断重叠的边界时包含等于的情况

3、在sort方法中，我本来想写成：

private void sort(List<Interval> intervals) {

不过这样做比较麻烦，因为是sort in place。所以我改为：

private List<Interval> sort(List<Interval> intervals) {

返回的是重新生成的​​List<Interval>​​对象

【附】
​[Leetcode] Merge Intervals and Insert Interval 合并间隔与插入间隔​​对Collection的排序方法要更为简单方便：

// 按照起点排序
Collections.sort(intervals, new Comparator<Interval>(){
    public int compare(Interval i1, Interval i2){
        return i1.start - i2.start;
    }
});

【代码】

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        //require
        List<Interval> ans=new LinkedList<Interval>();
        if(intervals==null)
            return ans;
        if(intervals.size()<1)
            return ans;
        //sort
        List<Interval> sorted=sort(intervals);
        //invariant
        int low=sorted.get(0).start,high=sorted.get(0).end;
        for(Interval i:sorted){
            if(high<i.start){
                ans.add(new Interval(low,high));
                low=i.start;high=i.end;
            }else{
                high=Math.max(high,i.end);
            }
        }
        ans.add(new Interval(low,high));
        //ensure
        return ans;
    }

    private List<Interval> sort(List<Interval> intervals) {
        int size=intervals.size();
        //base case
        if(size<2)
            return intervals;

        Interval mid=intervals.get(size/2);
        int pivot=mid.start;
        List<Interval> lefts=new LinkedList<Interval>(),rights=new LinkedList<Interval>(),ans=new LinkedList<Interval>(); 
        for(Interval i:intervals){
            if(i.start<pivot)
                lefts.add(i);
            else if(i.start>pivot)
                rights.add(i);
            else
                mid.end=Math.max(i.end,mid.end);
        }
        for(Interval i:sort(lefts)){
            ans.add(i);
        }
        ans.add(mid);
        for(Interval i:sort(rights)){
            ans.add(i);
        }
        return ans;
    }
}