import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author wuze
 * @desc ...
 * @date 2021-03-28 16:45:48
 */
public class 合并区间_新建结果集res存储_双指针指示区间左右元素_56 {
    class Solution {

        /*
        思路：     （sk：新建 结果集res对结果进行存储！）
        1、对区间的左边界进行排序（特殊排序，所以需要重写Comparator接口）
        2、使用双指针存储左右边界，遍历数组
            （1）如果区间可以扩大，则改变right的指向
            （2）如果区间不可扩大（两个区间没有交集），则将前一个区间加入结果列表，并更新left、right指向
        3、转换结果列表为二维数组形式，并return。

        */
        public int[][] merge(int[][] intervals) {
            if(intervals==null || intervals.length==0){
                //返回空二维数组
                return new int[0][];
            }

            //对原数组对 左区间 进行排序（重写Comparator接口）
        /*
        方法一：
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
*/
            //方法二：
            Arrays.sort(intervals,(interval1, interval2) -> interval1[0]-interval2[0]);

            //定义一个存储结果的List集合
            List<int []> res = new ArrayList<>();

            //初始化左右指针
            int left=intervals[0][0];
            int right=intervals[0][1];

            //从第二个区间开始
            for(int i=1;i<intervals.length;i++){
                //如果后一个区间的左元素>前一个区间的右元素
                //说明这两个区间没办法合并，则将上一个区间加入结果列表（注：是上一个区间）
                if(intervals[i][0]>right){
                    res.add(new int[]{left,right});
                    //更新left，right指向
                    left=intervals[i][0];
                    right=intervals[i][1];
                }else{
                    //否则，合并这两个区间
                    //也就是定住左指针，然后将右指针向后移动到后一个区间的右元素
                    //（注意！ 要看两个区间谁的右元素大，得指向大的那个右元素，所以要加上Math.max判断）
                    //比如 [[1,4],[2,3]] ，此时 应该输出[[1,4]] ， 而不是 [[1,3]] ！！！
                    right=Math.max(right,intervals[i][1]);
                }
            }
            //遍历完整，将最后一个 区间 加入 结果列表
            res.add(new int[]{left,right});
            return res.toArray(new int[][]{});
        }

    }

}