题解 | #合并区间#

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) {
        // write code here
        ArrayList<Interval> res = new ArrayList<>();
        if(intervals.size() == 0){
            return res;
        }

        // 根据start、end排序
        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 = 0;i < intervals.size();i++){
            Interval next = intervals.get(i);
            Interval last = res.get(count);

            // 判断有无交集
            if(last.end < next.start){
                res.add(next);
                count++;
            }else{
                res.remove(count);
                Interval combine = new Interval(last.start,next.end < last.end?last.end:next.end);
                res.add(combine);
            }
        }
        return res;
    }
}