题解 | #合并区间#

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
        if(intervals.isEmpty()){
            return intervals;
        }
		// 按起始元素排序
        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval interval, Interval t1) {
                return interval.start - t1.start;
            }
        });
        ArrayList<Interval> result = new ArrayList<>();
	  	// 第一个元素无需对比
        result.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
		  	// 将结果集里最新元素与当前元素对比
            Interval cur = intervals.get(i);
            Interval latest = result.get(result.size()-1);
            if (cur.start>latest.end){
			  	// 当前起始元素大于结果集最新结束元素时，无交集，直接加入结果集
                result.add(cur);
            } else {
			  	// 当前起始元素小于结果集最新结束元素时，有交集，结束值等于两个元素中最大的
                latest.end = Math.max(cur.end,latest.end);
            }
        }
        return result;
    }
}