合并区间

NC 37 合并区间

方法一：排序+双指针 对于两个区间[a,b] [c,d] 1、若 a < c < b,则这两个区间可合并，此时若b>d,则合并后的区间为[a,b],反之为[a,d] 2、若 c > b, 则合并不了。 总共只有以上这两种情况。 所以对于上面，我们可以将区间的起点做排序，即 a < c < ....，排成类似情况 用到Collections中的sort函数去排序，代码如下

public ArrayList<interval> merge(ArrayList<interval> intervals) {
        ArrayList<interval> res = new ArrayList<>();
        Collections.sort(intervals,(a,b)->a.start-b.start);
        int len = intervals.size();
        int i = 0;
        //下面举例子
        while(i < len){
            int left = intervals.get(i).start; //获得起点  a
            int right = intervals.get(i).end;  //获得终点  b
            //例如：c <= b，则可以合并
            while(i < len-1 && intervals.get(i+1).start <= right){
                // 看b大还是d大，区间则为哪个
                right = Math.max(right,intervals.get(i+1).end);
                i++; // i继续遍历下一个区间，看能不能继续合并
            }
            //合并完的区间放进去返回集合中
            res.add(new Interval(left,right));
            //以下一个为合并的区间为开始区间继续合并
            i++;
        }
        return res;
    }

方法二：排序 + 模拟 算法思路 比较容易想到的是先按照每个区间的起始值排序，再采用模拟法，将区间进行合并。

代码实现

import java.util.*;
/**
 * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, (v1, v2)->v1.start - v2.start);
        ArrayList<Interval> res = new ArrayList<Interval>();
        int idx = -1;
        for(Interval interval : intervals){
            if(idx == -1 || interval.start > res.get(idx).end){ //若数组为空，或当前区间的起始位置小于结果list中最后区间的终止位置
                //不合并，直接将当前区间加入结果list
                res.add(interval);
                idx ++;
            }else{    //合并，选择较大的数作为最后区间的终止位置
                res.get(idx).end = Math.max(interval.end, res.get(idx).end);
            }
        }
        return res;
    }
}

算法复杂度

时间复杂度：$O(NlogN)O(NlogN)$， n为未进行合并的区间数。

空间复杂度：$O(N)O(N)$, n为合并完成后的区间数。