LEETCODE 56. 合并区间

LEETCODE 56. 合并区间

题目描述

给出一个区间的集合,请合并所有重叠的区间。
示例 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)]

至于怎么排序,我们用每个区间的第一个元素来排序,即比较x1y1

排序完之后,以两两合并的方式,把数组元素遍历一遍就可以求出最终结果了。
时间复杂度,排序一次是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
                                                                     

 

(全文完)

2 次阅读

发表评论

电子邮件地址不会被公开。