56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }

        Arrays.sort(intervals, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });


        List tmp = new ArrayList<>();

        int left = intervals[0][0], right = intervals[0][1];

        for (int i = 1; i < intervals.length; ++i) {
            if (intervals[i][0] > right) {
                tmp.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            } else {
                right = Math.max(right, intervals[i][1]);
            }
        }

        tmp.add(new int[]{left, right});


        int[][] ret = new int[tmp.size()][2];

        for (int i = 0; i < tmp.size(); ++i) {
            ret[i] = tmp.get(i);
        }

        return ret;
    }
}