题目 给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 示例 1: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 示例 2: 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。 https://leetcode-cn.com/problems/insert-interval/ 解法1 解法1的思路很简单，因为区间无重叠且按照起始点排序，那么我们可以借助56题的方法，先将newInterval插入到合适的位置，然后用56题方法合并区间。合适的位置指的是intervals[i].start <= newInterval.start但intervals[i+1].start > newInterval.start。 题目函数签名为“public int[][] insert(int[][] intervals, int[] newInterval) ”，因为插入新的区间会改变区间个数，使用int[][]不方便实现insert操作，所以我们使用容器List<int[]>来存放区间。题目要求结果存放在int[][]型数组中，我们在输出时还需要将List转换成Array。题目全部代码如下，时间复杂度O(n)，空间复杂度O(n)。 解法2 解法2将intervals拆分成3部分，左半部分与newInterval没有交集，右半部分与newInterval没有交集，中间部分是与newInterval有交集的区间。假设前i个intervals中的区间与newInterval没有交集，第i+1个interval与newInterval有交集，我们将这两个区间合并形成[start, end]，然后i++寻找下一个区间，直到找到与newInterval不相交的区间为止。此时，我们将合并后的区间[start, end]追加到结果集，然后将intervals中剩余的区间追加到结果集。 我们分析下interval[i]与newInterval不相交，但interval[i+1]与newInterval相交有哪些情况 图1列出了区间相交的集中情况。从图中可以看出，当intervals[i+1]与newInterval合并的时候，我们需要取两者左边界的最小值，右边界的最大值。 在合并的过程中，我们需要判断什么时候终止。如图2所示，终止条件是当newInterval的后沿小于第i+1个区间的前沿，即newInterval.end < intervals[i+1].start。那我们用不用判断newInterval的前沿与第i个区间后沿的关系呢？是不用的！因为前面我们提到，首先寻找与newInterval不相交的区间，加入到结果集，在这个过程中，我们的判断条件就是intervals[i].end < newIntervals.start。当发生合并的时候一定有intervals[i].end >=…