QUESTION:

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2:

输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

EXPLANATION:

思路：从题目来看的话，看起来题目给出的数组都是按照顺序来的，但是其实并不是，所以我们需要重新进行排列。想法是，遍历每个区间，将区间进行标记，最后再进行所有区间的合并。这样遇到了一个问题，就是无法区分1-4，5-6的情况，那么就需要引入第二个变量来标记是否是相交的。
1.将所有的区间按照第一个数进行排序
2.创建一个二维数组用来标记，0位置表示是否被涂抹，1位置表示涂抹的颜色
3.遍历区间，对所有的区间进行涂抹，如果当前位置已经被涂抹，那么，这一整个区间就都被涂抹为之前的颜色
4.对涂抹后的数组进行遍历，如果是同一个颜色的涂抹，就添加到结果list中
5.最后再将list转化为二维数组

SOLUTION:

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals==null || intervals.length==0) return new int[0][];
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int length = 0;
        for(int i = 0;i<intervals.length;i++) length = Math.max(length,intervals[i][1]);
        int[][] index = new int[length+1][2];
        for(int i = 0;i<intervals.length;i++){
            int[] tmp = intervals[i];
            int pre = i;
            if(index[tmp[0]][0]!=0) pre = index[tmp[0]][1];
            for(int j = tmp[0];j<=tmp[1];j++){
                index[j][0] = 1;
                index[j][1] = pre;
            }
        }
        int start = 0,end = start+1;
        ArrayList<int[]> list = new ArrayList<>();
        while (end<index.length){
            while (start<index.length && index[start][0]==0) start++;
            end = start+1;
            while (end<index.length && index[end][0]==1 && index[end][1]==index[end-1][1]) end++;
            int[] tmp = new int[2];
            tmp[0] = start;
            tmp[1] = end-1;
            list.add(tmp);
            start = end;
        }
        int[][] result = new int[list.size()][];
        for(int i = 0;i<result.length;i++) result[i] = list.get(i);
        return result;
    }
}