leetcode经典例题——56.合并区间

56.合并区间

题目描述：

思路：咱们看到合并区间就先不管他有几个区间的集合，假设我们现在有两个区间的集合：

如果两个区间[1,3]、[2,6]，因为3>2，3<6所以合并区间[1,6]；

如果两个区间[1,7]、[2,6]，因为7>2，7>6所以合并区间[1,7]；

如果两个区间[1,3]、[4,6]，因为3<4所以不用合并，还是原来两个区间[1,3]、[4,6]；

当我们进行合并的时候我们只需要考虑这三种情况，所以现在的问题就是如何把若干个区间转化为上面这种比较的情况；

我们来看看带码就能理解：

public int[][] merge(int[][] intervals) {
        //先给数组排序
        Arrays.sort(intervals,(a,b)->{return a[0]-b[0];});
        //用来装合并好的区间
        int[][] res = new int[intervals.length][2];
        int index = 0;
        for (int i = 0,j ; i < intervals.length;) {
            j = i+1;
            while (j<intervals.length && intervals[i][1] >= intervals[j][0]){
                if(intervals[i][1] <= intervals[j][1])
                    intervals[i][1] = intervals[j][1];
                else intervals[j][1] = intervals[i][1];
                j++;
            }
            res[index][0] = intervals[i][0];
            res[index][1] = intervals[j-1][1];
            i = j;
            index++;
        }
        return  Arrays.copyOf(res, index);
    }

时间复杂度：O(n)，虽然是双重循环，但只要遍历完数组就结束了

空间复杂度：O(n)

总结：这道题是一道比较偏逻辑的题目，没有用到什么算法，但作为leetcode热题100，咱们宁可错杀一千，不可放过一个，都给他刷了_