1、前言

2、思路

这道题的思路很朴素，就是先按照数组左边降序排列，如果相同再按照数组右边降序排列（因为数组没有说有序，所以必须按照左边降序排列，至于右边降序排列其实可有可无），所以此题最低的时间复杂度必定为 O(logn)。

排列完之后，直接比较此时遍历到的数组 interval 的左端与 pre 的右端，如果 interval[0] > pre[1]，说明数组无重合，直接加入。否则，应该取 pre[1] 与 interval[1] 中最大的。

其实 leetcode 有很多题偏向工程思维，没有那么多奇淫技巧抑或是各种递归、动态规划之类的，非常培养自身的工程能力。所以，当一道题你觉得没有什么算法能套进去后，可以试着用最普通的工程思维来做，往往是最优解。

3、代码

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

        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                int res = o1[0] - o2[0];
                if(res == 0){
                    res = o1[1] - o2[1];
                }
                return res;
            }
        });

        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);
        for(int i = 1; i < intervals.length; i++){
            int[] pre = list.get(list.size() - 1);
            int[] interval = intervals[i];

            if(pre[1] < interval[0]){
                list.add(interval);
            }else {
                pre[1] = Math.max(pre[1], interval[1]);
            }
        }

        return list.toArray(new int[][]{});
    }
}