题解 | #合并区间#

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类ArrayList
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        if(intervals.size()==0)
            return res;
        Collections.sort(intervals,new Comparator<Interval>(){
            public int compare(Interval o1,Interval o2){
                if(o1.start!=o2.start)
                    return o1.start-o2.start;
                else
                    return o1.end-o2.end;
            }
        });
        res.add(intervals.get(0));
        int count=0;
        for(int i=1;i<intervals.size();i++){
            Interval o = intervals.get(i);
            Interval temp = res.get(count);
            //如果两区间不重叠
            if(o.start>temp.end){
                res.add(o);
                count++;
            }
            //如果两区间不重叠
            else{
                res.remove(count);
                Interval newInterval = new Interval(temp.start,o.end);
                if(o.end<temp.end)
                    newInterval.end=temp.end;
                res.add(newInterval);
            }
        }
        return res;
    }
}