每天一道算法：合并区间

53、合并区间

题目

给定一个区间的数组，将所有重叠的区间进行合并。

示例1：

示例2：

思路

先按照每个区间的起点排序，然后从小到大扫描。

每次扫描，查看与前一个是否有重叠，如果是则合并成1个。

需要提前排序的原因是，这样只需要查看与前一个是否重叠，不需要查看更往前的，因为之前的都处理完毕。

比如一个数组按照区间的起点排序后为：[[1,3],[2,4],[3,5]]。

那么从第二个区间[2,4]开始，查看是否与前面的[1,3]重合，重合了则合并为[1,4]。

继续扫描第三个区间[3,5]，查看是否与前面的[1,4]重合，重合了则合并为[1,5]。

因此最后三个区间合并为一个，结果输出 [[1,5]]。

代码

python实现