题解 | #合并区间#

题目 合并区间

日期 2022/03/20

思路

先自定义比较器，根据interval的start比较大小；合并区间时，将已经按升序排序的元素一个个加入，若加入的元素的start小于前一个元素的end时，则将这两个区间合并，起点为前一个元素的star，终点为这两个元素end的较大值。若若加入的元素的start不小于前一个元素的end，则直接加入

代码

import java.lang.Math;
/**
 * 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) {
        intervals.sort(new Comparator<Interval>(){
            public int compare(Interval a,Interval b){
                return a.start-b.start;
            }
        });
        
        ArrayList<Interval> res = new ArrayList<>();
        for(Interval val : intervals){
            if(res.isEmpty())
                res.add(val);
            else if(res.get(res.size()-1).end<val.start)
                res.add(val);
            else{
                res.add(new Interval(res.get(res.size()-1).start,Math.max(res.get(res.size()-1).end,val.end)));
                res.remove(res.get(res.size()-2));
            }
        }
        return res;
    }
}