题目描述

给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题解

一堆区间可能不好找出他们之间的关系，我们先将范围缩小，看看只有两个区间的情况
假设有区间[x1,x2],[y1,y2]
如果把他们映射到坐标轴上，可能有下面一些情况
首先是[x1,x2]和[y1,y2]完全不相交(注意，区间在坐标轴上显示出来应该是一条线，画成矩形只是为了方便演示)

第二种情况是包含，[y1,y2]被包含在[x1,x2]内，或者[x1,x2]被包含在[y1,y2]内

第三种情况是部分相交，[x1,x2]和[y1,y2]有部分重叠

根据上面的例子可以发现有6种不同的状态，但有一半是重复的，比如[x1,x2]和[y1,y2]不相交，[y1,y2]和[x1,x2]不相交，这就可以算作是一种，只需要将这两个区间排好序就可以了，这样就省掉一半的重复情况。
那么留下来的就是三种不同的情况:

1. [x1,x2]和[y1,y2]不相交，这两个区间都会保留下来
2. [x1,x2]被包含在[y1,y2]内，这两个区间需要合并
3. [x1,x2]和[y1,y2]有部分重叠，这两个区间需要合并

第一种情况很好判断，只要x2<y1就说明这两个区间完全不相交，此时就把这两个区间都保留下来即可。

第二种和第三种情况，都是满足y1<x2

y1<x2时有两种结果，区间的开头当然还是x1，区间的结尾我们取max(x2,y2)
所以第二、第三种情况时，我们新合并的区间范围就是:
[x1, max(x2,y2)]

至于怎么排序，我们用每个区间的第一个元素来排序，即比较x1和y1。

排序完之后，以两两合并的方式，把数组元素遍历一遍就可以求出最终结果了。
时间复杂度，排序一次是O(NlogN)，再遍历一次是O(N)，总时间就是O(NlogN)
空间复杂度是 O(N)

java代码:

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals==null || intervals.length==0) {
            return intervals;
        }
        //先按区间的一个元素排序一遍
        Arrays.sort(intervals, (x,y)->x[0]-y[0] );
        List<int[]> arr = new ArrayList<int[]>();
        arr.add(intervals[0]);
        for(int i=1;i<intervals.length;++i) {
            //[x1,x2]和[y1,y2]比较，如果x2<y1说明这两个区间不想交
            if(arr.get(arr.size()-1)[1] < intervals[i][0]) {
                arr.add(intervals[i]);
            }
            //否则，将这两个区间合并为 [x1,max(x2,y2)]
            else {
                arr.get(arr.size()-1)[1] = Math.max(arr.get(arr.size()-1)[1],intervals[i][1]);
            }
        }
        return arr.toArray(new int[arr.size()][2]);
    }
}
                                                                                                 

python代码:

class Solution(object):
    def merge(self, intervals):			
        if not intervals:
            return []
        # 先按区间的一个元素排序一遍	
        intervals = sorted(intervals,key=lambda x:x[0])
        arr = [intervals[0]]
        for i in xrange(1,len(intervals)):
            # [x1,x2]和[y1,y2]比较，如果x2<y1说明这两个区间不想交
            if arr[-1][-1]<intervals[i][0]:
                arr.append(intervals[i])
            # 否则，将这两个区间合并为 [x1,max(x2,y2)]	
            else:
                arr[-1][-1] = max(arr[-1][-1],intervals[i][-1])
        return arr