题解 | 合并区间

排序 + 模拟

算法思路

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

代码实现

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(n)， n为未进行合并的区间数。
空间复杂度：O(n), n为合并完成后的区间数。