每天一道算法：插入区间

54、插入区间

题目

给定一系列不重复的区间，要求将一个新的区间插入到这些集合中（如果有必要，则合并）。

示例1：

示例2：

思路

本题与

每天一道算法：合并区间

很相似，不同之处在于，本题需要先插入新区间，然后再进行合并。

在插入区间之前，首先要找到需要插入到哪个位置：从左到右扫描，然后比较新区间和数组内区间的起始点的大小即可找到。

然后将新区间插入到数组（插入的过程可能会涉及到与上一个区间的重叠合并），插入之后，剩余的子数组可能会与这个区间有重叠部分，需要依次进行扫描判断。

比如示例2，先查询到需要插入的位置：[3,5]的后面，然后进行插入，之后数组变为[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]。

然后从[4,8]开始往后一次扫描，每次扫描时判断是否与前一个区间有重叠，如果有重叠则进行合并。

最终[3,5],[4,8],[6,7],[8,10]合并为[3,10]，因此最后结果为[[1,2],[3,10],[12,16]]。

代码

python实现