题解 | 合并区间

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) {
        if (intervals.size() == 0) {
            return new ArrayList<Interval>();
        }
        intervals.sort((a,b) -> {
            return a.start - b.start;
        });
        // write code here
        ArrayList<Interval> mergeArray = new ArrayList<>();
        mergeArray.add(intervals.get(0));

        int last = 0;

        for (int i = 1; i < intervals.size();i++) {
            Interval inter = intervals.get(i);
            Interval mergeInter = mergeArray.get(last);
            if (mergeInter.end >= inter.start) {
                //合并
                mergeInter.end = Math.max(mergeInter.end,inter.end);

            } else {
                mergeArray.add(inter);
                last++; 

            }

        }


        return mergeArray;

    }

    
}

1、按区间起点排序，然后就可合并相邻的区间（假如交叉），排序可保证所有可合并的区间都连续。

2、具体操作：若交叉，更新合并后数组最后一个区间的结尾end取mergeArray[last]，intervals[i]最大的一个（相当于合并、插入mergeArray[last]）。

若无交叉，则intervals[i]插入mergeArray结尾，last++。继续遍历intervals，重复2;

3、mergerArray初始为排序后的第一个区间；注意判断入参为空数组的情况。