Merge Intervals
你会得到一组区间，每个区间都是从起点到终点的一段整数范围。将每组重叠的区间合并为一个覆盖整组区间的区间，并按起点排序后返回合并结果。仅相接的区间也算重叠，例如 [1, 4] 和 [4, 5]。
这些区间由两个长度相同的数组表示：区间 i 是 [starts[i], ends[i]]。你需要返回一个二维数组，也就是由 [start, end] 对组成的列表。
函数
- startsinteger-array
- 每个区间的起点
- endsinteger-array
- 每个区间的末尾与其起点位于相同索引处
- 返回值integer-2d-array
- 合并后的区间，以 [start, end] 对表示，并按起点排序
约束条件
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- 这些区间以任意顺序到达。
- 仅在端点处相接的区间也算重叠。
示例
- 输入
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- 输出
- [[1, 7], [12, 14]]
- 解释
- 按开始位置排序后，[1, 4] 与 [3, 6] 重叠，而后者又与 [5, 7] 重叠，因此这三个区间合并为 [1, 7]。[12, 14] 的起点在 7 之后，因此保持独立。
- 输入
- starts = [6, 1]ends = [9, 6]
- 输出
- [[1, 9]]
- 解释
- 这两个区间是 [6, 9] 和 [1, 6]。它们共享点 6，并且端点相接也算重叠，所以合并为 [1, 9]。
进阶
这些区间已经按起点排序并合并，你需要再添加一个新区间。你能在 O(n) 时间内返回合并后的列表，而不再排序吗？
提示
逐个打开提示，每个都会多透露一点。
先为每个开始时间配对对应的结束时间，这样你处理的就是完整的时间区间，而不是两个分开的数组。
按起点对区间排序。之后，一个区间只可能与它前面的紧邻分组重叠，不会与更靠前的分组重叠。
遍历已排序的区间，同时保留最后一个合并后的区间。如果下一个区间的起点小于或等于它的终点，就将它的终点设为两个终点中较大的那个。否则，当前区间组就结束，下一个区间会开启一个新的区间组。
题解
按任意顺序合并区间需要反复遍历，因为每次合并都会扩大区间，使它能够延伸到你已经检查过的区间。改为按起点排序。这样，区间只可能与正在合并的区间组重叠，一次遍历就能完成任务。
不断合并重叠的区间对，直到不再发生变化
结果正确，但无法在最大的测试中运行完毕
思路
当 c ≤ b 且 a ≤ d 时，区间 [a, b] 和 [c, d] 重叠，而 [min(a, c), max(b, d)] 覆盖这两个区间。每次合并都会移除一个区间，所以这个过程会停止；当完整遍历一遍后没有发现重叠时，剩下的任意两个区间都不再共享任何点。只遍历一遍还不够：合并后的区间更宽，可能会延伸到本轮中较早时曾与其较小部分比较过的区间。
一轮遍历会比较大约 n²/2 对区间，最多可能需要 n 轮：O(n³)。遍历一遍 10^4 个区间，就已经需要进行 5 × 10^7 次比较。
算法
- 复制
starts和ends，并用n记录有效区间的数量。 - 将每个区间
i与它后面的每个区间j进行比较。如果它们重叠，就扩展i以覆盖j，将最后一个有效区间移到j的位置，并将n减 1。 - 合并后，再次检查位置
j，因为现在那里存放的是另一个区间。 - 重复遍历，直到某次遍历没有进行任何合并。
- 将每个有效起点与对应的终点配对，按起点对这些配对排序并返回。
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))按起点排序，然后扫描一次
思路
按起点排序后，下一个区间的起点不会早于最后一组中的任何区间，而最后一组的终点是 e。如果它的起点小于或等于 e，它就与这一组合并（重叠或相接），并将 e 更新为两个终点中较大的那个。如果它的起点晚于 e，那么之后的区间也无法延伸回这一组，因为它们的起点更靠右。这一组就此结束，该区间开启新的一组。
排序的时间复杂度为 O(n log n)，扫描过程会遍历每个区间一次。各组从左到右结束，因此结果按起点排序。
算法
- 将每个起点与对应的终点配对：区间
i是[starts[i], ends[i]]。 - 按起点对这些配对排序。
- 遍历排好序的配对。如果结果为空，或者当前配对的起点晚于最后一个合并区间的终点，就将当前配对作为新区间追加进去。
- 否则，将最后一个合并区间的终点设为它当前的终点和当前配对终点中较大的那个值。
- 返回合并后的列表。
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
易错点和边界情况
- 使用
<而不是≤进行比较。像[1, 4]和[4, 5]这样相接的区间必须合并。 - 将结束位置设为新区间的结束位置，而不是两个区间中较大的结束位置。
[1, 10]后面跟着[2, 3]时，必须仍为[1, 10]。 - 单独对
starts排序，然后在新位置读取ends，这样一个起点就会配上另一个区间的终点。应先将它们配对，或对索引排序。 - 与前一个输入区间比较，而不是与最后一个合并后的区间比较。在
[1, 10]、[2, 3]、[4, 5]中，第三个区间位于[1, 10]内，尽管它与[2, 3]不相接。 - 在 C 中，没有将
*returnSize设为合并后的区间数量，也没有将每一列的大小设为 2。
常见问题3
合并区间的时间复杂度是多少？
对于 n 个区间，排序和扫描方案的时间复杂度为 O(n log n)：排序需要 O(n log n)，扫描需要 O(n)。它需要 O(n) 的额外空间来存储排序后的数对和结果。
为什么按起点而不是终点对区间排序？
按起点排序后，一个区间只能与正在构建的组重叠，因此只需将它与该组的终点比较一次，就能确定所有情况。按终点排序后，后面的区间可能会在已关闭的组之前开始：[5, 6] 排在 [1, 10] 前面，向前扫描会错误地将 5 保留为起点。
你能在不使用额外空间的情况下合并区间吗？
可以，前提是你可以修改输入。原地对区间进行排序，然后将合并后的每个区间写到同一个数组的前面，并记录最后一个写入区间的索引。时间复杂度仍为 O(n log n)，额外空间只取决于你的语言使用的排序算法。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def mergeIntervals(starts, ends):
# 在这里编写代码测试 #1
测试 #2
参数
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
预期输出
[[1, 7], [12, 14]]