class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));
        List<int[]> list = new LinkedList<>(Arrays.asList(intervals));
        int i = 0;
        int j = 1;
        while(i <list.size() && j < list.size()){
            final int[] ii = list.get(i);
            final int[] jj = list.get(j);
            if(ii[1]>=jj[0]){
                ii[1] = Math.max(ii[1], jj[1]);
                list.remove(j);
            }else{
                i++;
                j++;
            }
        }
        return list.toArray(new int[0][0]);
    }
}

//new 一个新数组，将范围内的数都填到新数组中值设为1，然后遍历数组，连续为1的范围就是所求的范围。
class Solution {
    public int[][] merge(int[][] intervals) {
        int len = 0;
            for(int[] arr : intervals){
                if(arr[0] > len) len = arr[0];
                if(arr[1] > len) len = arr[1];
            }
            // new 一个新数组，长度是intervals 最大值的两倍，把intervals范围内的数*2填入数组
            // 【避免出现[1,3][4,5]，3和4中间是未覆盖部分，转化为[2,6][8,10]，6和8不连续】
            int[] data = new int[(len+1)*2];
            for(int[] arr : intervals){
                for(int i = arr[0]*2;i <= arr[1]*2;i++){
                    data[i] = 1;
                }
            }
            List<int[]> res = new ArrayList<>();
            for(int i = 0;i < data.length;i++){
                if(data[i] == 1){   // 如果连续为1，则肯定是覆盖后的范围
                    int start = i/2;
                    while(i < data.length && data[i] == 1){
                        i++;
                    }
                    int end = (i-1)/2;
                    res.add(new int[]{start, end});
                }
            }
            return res.toArray(new int[res.size()][2]);
    }
}