LC56 - 合并区间

两个区间合并一共有六种可能

首先要把它们都转换成第一行的三种情况，那么就需要保证第一个区间的开始小于第二个区间的开始，于是我们需要把所有区间按开始的大小排序，之后再按这三种情况讨论。
以下是代码

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0 || intervals == null) return intervals;
        //将所有区间按区间开始大小排序
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        //用一个list来存放所有区间
        List<int[]> list = new ArrayList<>();
        //先将第一个元素设为cur区间
        int[] cur = intervals[0];
        for(int i=1; i<intervals.length; i++){
            //情况3，两区间不想交，直接将当前cur区间提交并更新cur区间
            if(intervals[i][0] > cur[1]){
                list.add(cur);
                cur = intervals[i];
            }else{
                //情况1或2，cur区间的结束值取两个区间结束值的最大值
                cur[1] = Math.max(cur[1], intervals[i][1]);
            }
        }
        list.add(cur);
        int[][] ans = new int[list.size()][2];
        //将list重整为数组输出
        for(int i=0; i<list.size(); i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}