LeetCode算法笔记56：合并区间

题目描述

给出一个区间的集合，请合并所有重叠的区间。

输入: intervals = [ [1,3] , [2,6] , [8,10] , [15,18] ]

输出: [ [1,6] , [8,10] , [15,18] ]

解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

本文答案参考自LeetCode官方题解。

其实这就是我们小学二年级（[看]）就学过的求 交集

1. 先将这些区间按左端点进行排序
2. 将第一个区间加到 答案区间（设为 merged） 中
3. 从第二个区间开始遍历，
1. 如果当前区间的左端点 小于 merged 的最后一个区间的右端点，则将当前区间加到merged 的最后一个区间中（操作是：将 merged 的最后一个区间的右端点 设置为 max{当前区间的右端点，merged 的最后一个区间的右端点 } ）
2. 如果当前区间的左端点 大于 merged 的最后一个区间的右端点，则直接将当前区间加到merged 的后面（因为 与merged 的前面的区间 不产生交集）

[耶]

这种情况画数轴会比较好理解。我懒得画了。[捂脸]

至于为什么可以这样，嘻嘻。n(*≧▽≦*)n

不过要注意的是：这里的时间复杂度主要取决于排序的时间复杂度。

​​[来看我][来看我][来看我]