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]
不相交,这就可以算作是一种,只需要将这两个区间排好序就可以了,这样就省掉一半的重复情况。
那么留下来的就是三种不同的情况:
-
[x1,x2]
和[y1,y2]
不相交,这两个区间都会保留下来 -
[x1,x2]
被包含在[y1,y2]
内,这两个区间需要合并 -
[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
(全文完)
2 次阅读