Insert Interval
你会得到两个按起点排序的数组，用来表示区间：区间 i 是 [starts[i], ends[i]]，任意两个区间都不重叠，也不相接。插入新区间 [newStart, newEnd]，将它与所有重叠或相接的区间合并，并返回所有按起点排序的 [start, end] 区间对。
如果一个区间的终点与另一个区间的起点相同，它们就相接，例如 [2, 4] 和 [4, 8]，相接的区间会合并。[1, 2] 和 [3, 4] 没有共享任何点，所以它们保持分开。
函数
- startsinteger-array
- 每个区间的起点，按升序排列
- endsinteger-array
- 每个区间的末尾，与起点匹配
- newStartinteger
- 要插入的区间的起始位置
- newEndinteger
- 要插入的区间的末尾
- 返回值integer-2d-array
- 插入后的区间以 [start, end] 对表示，并按 start 排序
约束条件
1 ≤ starts.length == ends.length ≤ 20000 ≤ starts[i] ≤ ends[i] ≤ 105ends[i] < starts[i+1]：区间按起始位置排序，且任意两个区间都不重叠也不相接。0 ≤ newStart ≤ newEnd ≤ 105
示例
- 输入
- starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
- 输出
- [[1, 3], [5, 12], [15, 18]]
- 解释
[6, 11]与[5, 7]和[10, 12]重叠，因此这三个区间合并为[5, 12]。[1, 3]在 6 之前结束，[15, 18]在 12 之后开始，因此这两个区间都保持不变。
- 输入
- starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
- 输出
- [[2, 9]]
- 解释
[4, 8]在 4 处与[2, 4]相接，在 8 处与[8, 9]相接，因此这三个区间合并为[2, 9]。
- 输入
- starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
- 输出
- [[1, 2], [5, 6], [9, 10]]
- 解释
[5, 6]位于 2 和 9 之间的间隙中，也不接触任何一个相邻项，因此会插入它们之间，且不会合并任何内容。
进阶
如果你连续插入多个区间，怎样存储它们，才能让每次插入的成本为 O(log n)，再加上每个被合并的旧区间所需的一步？
提示
逐个打开提示，每个都会多透露一点。
旧区间已经排序，并且彼此分开。新区间可能会改变其中哪些区间？这些区间可能位于列表的什么位置？
这些区间分为三段：结束位置早于
newStart的区间，与[newStart, newEnd]重叠或相接的区间，以及开始位置晚于合并后区间结束位置的区间。中间这段是一个连续块。遍历列表一次。复制结束位置早于
newStart的区间。然后，当下一个区间的开始位置小于或等于你正在构建的新区间的结束位置时，扩大新区间以覆盖它。追加新区间，然后复制剩下的区间。
题解
旧区间已经排好序，并且彼此分开，因此只有新区间可能引发合并。这会把列表分成三段：在新区间开始前结束的区间、与新区间重叠或相接的区间，以及在新区间结束后开始的区间。复制第一段，把中间一段合并成一个区间，再复制最后一段。遍历一遍即可，无需排序。
添加它，然后再次合并所有内容
思路
复用合并区间：添加新区间，按起点对全部 n+1 个区间排序，然后遍历它们，并暂存最后一个合并后的区间。排序后，一个区间只可能与它前面的那组区间重叠，因此，当下一个区间的起点小于或等于暂存区间的终点时，就延长终点；否则，出现间隙，开始一个新区间。
为了修正列表中一处乱序的问题，排序需要花费 O(n log n)，而且它忽略了旧区间之间从不合并这一点。
算法
- 将每个起点与对应的终点配对，并将
[newStart, newEnd]添加到列表中。 - 按起点对区间排序。
- 按顺序遍历这些区间，并保留最后一个合并后的区间。
- 如果下一个区间的起点小于或等于当前区间的终点，就将当前区间的终点更新为两个终点中较大的那个。
- 否则，将下一个区间作为一个新的合并区间添加进去。返回合并后的列表。
def insertInterval(starts, ends, newStart, newEnd):
intervals = list(zip(starts, ends))
intervals.append((newStart, newEnd))
intervals.sort()
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # overlaps or touches: stretch
else:
merged.append([start, end]) # a real gap: a new interval begins
return merged分三部分完成一遍
思路
列表已排序，且各区间彼此分开，因此与新区间相交的区间会连续排列。连续部分之前的所有区间都满足 ends[i] < newStart：它们在新区间开始之前就结束了。这里使用严格比较，因为结束位置恰好为 newStart 的区间会与新区间接触，必须合并。
在连续部分中，满足 starts[i] ≤ mergedEnd 的区间与正在构建的区间重叠或接触，因此会将它扩展到更小的起点和更大的终点。第一个起点大于 mergedEnd 的区间标志着连续部分结束，因为后续每个区间的起点都更靠右。如果连续部分为空，就单独插入新区间。在第一个示例中，复制 [1, 3]，[5, 7] 和 [10, 12] 将 [6, 11] 扩展为 [5, 12]，然后复制 [15, 18]。每个区间只检查一次：时间复杂度为 O(n)，除了结果之外不需要额外内存。
算法
- 当
ends[i] < newStart时，将区间复制到结果中。 - 设置
mergedStart = newStart和mergedEnd = newEnd。 - 当
starts[i] ≤ mergedEnd时，将mergedStart设为较小的起点，将mergedEnd设为较大的终点，然后继续。 - 追加
[mergedStart, mergedEnd]。 - 复制剩余的区间并返回结果。
def insertInterval(starts, ends, newStart, newEnd):
n = len(starts)
result = []
i = 0
# 1. Intervals that end before the new one starts stay as they are.
while i < n and ends[i] < newStart:
result.append([starts[i], ends[i]])
i += 1
# 2. Intervals that overlap or touch the new one fold into it.
mergedStart, mergedEnd = newStart, newEnd
while i < n and starts[i] <= mergedEnd:
mergedStart = min(mergedStart, starts[i])
mergedEnd = max(mergedEnd, ends[i])
i += 1
result.append([mergedStart, mergedEnd])
# 3. Intervals that start after the merged one ends stay as they are.
while i < n:
result.append([starts[i], ends[i]])
i += 1
return result
易错点和边界情况
- 用于判断区间是否相接的不等式有误。在第一个循环中使用
ends[i] ≤ newStart，或在第二个循环中使用starts[i] < mergedEnd，都会让[2, 4]和[4, 8]分开。第一个判断应使用严格不等式，第二个则不应使用。 - 与
mergedEnd + 1比较。这会合并[1, 2]和[3, 4]，但它们没有共同点。 - 将
newStart保留为合并后的起点。[6, 11]的起点在[5, 7]内部，所以结果应从 5 开始。 - 只有在新区间与其他区间重叠时才添加它。如果新区间落在空隙中或位于任一端之外，例如
[5, 6]，中间循环就不会运行，但仍必须添加新区间。 - 检查
i < n之前就读取starts[i]。如果新区间延伸到最后一个区间之后，索引就会越界。
常见问题3
插入区间的时间复杂度是多少？
单次遍历的解法运行时间为 O(n)，因为每个区间只会被复制或合并一次，并且需要 O(n) 的空间来存储最多包含 n+1 个区间的结果。添加区间并重新排序需要 O(n log n)。
插入区间和合并区间有什么不同？
合并区间从一个未排序的列表开始，其中任意区间都可能与其他区间重叠，因此需要先排序。这里的列表已经排序，而且旧区间之间不会相接，所以只有新区间会触发合并，并且与它合并的区间会连续排列。遍历一遍就够了。
如何检查两个区间是否重叠？
[a, b] 和 [c, d] 当且仅当 a ≤ d 且 c ≤ b 时共享一个点。这会将 [2, 4] 和 [4, 8] 这类相接的区间也算作重叠，这正是本题要求的。如果要让相接的区间彼此分开，则使用 a < d 和 c < b。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def insertInterval(starts, ends, newStart, newEnd):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
starts = [1, 5, 10, 15] ends = [3, 7, 12, 18] newStart = 6 newEnd = 11
预期输出
[[1, 3], [5, 12], [15, 18]]