class Solution {
    // 按照第数组中的第一个元素排序，排序之后
    // 后一个数组的左端点如果小于前一个数组的右端点则需要合并
    // 两种情况：1.后一个数组的左端点小于前一个数组的右端点，则直接合并前一个数组
    // 2.后一个数组的左端点大于于前一个数组的右端点，则取前一个数组的左端点和后一个数组的右端点
    // 由于合并之后的元素个数我们并不知道，所以一开始要用一个list存储结果
    public int[][] merge(int[][] intervals) {
       int n = intervals.length; // 列已知为2
       Arrays.sort(intervals, (a,b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
       List<int[]> merge = new ArrayList<>();
       for (int i = 0; i < n; i++) { // intevlas[i][1]与merge中最后一个数组的[1]进行比较
            if (merge.isEmpty() || intervals[i][0] > merge.get(merge.size() - 1)[1]) {
                merge.add(intervals[i]);
            } else {
                merge.get(merge.size() - 1)[1] = Math.max(merge.get(merge.size() - 1)[1], intervals[i][1]);
            }
       }
    int row = merge.size();
    int[][] res = new int[row][2];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < 2; j++) {
            res[i][j] = merge.get(i)[j];
        }
    }
    return res;    
    }
}