给定两个已经按照区间起点排序、且各自内部不存在重叠区间的区间列表 A 和 B。每个区间由 [start, end] 表示，要求将两个列表中的所有区间合并成一个新的区间并集。如果两个区间存在重叠，则将它们合并成覆盖范围更大的单个区间；如果两个区间互不重叠，则分别保留。最终返回按照起点排序且不存在重叠的区间列表。
示例 1：
输入：
A = [[1, 2], [3, 9]]
B = [[4, 6], [8, 10], [11, 12]]
输出：
[[1, 2], [3, 10], [11, 12]]
解释：
[1, 2] 与 [3, 9] 首先按照起点顺序进入处理流程。[1, 2] 与 [3, 9] 不重叠，因此保留 [1, 2]。[3, 9] 与 [4, 6] 重叠，合并后仍然覆盖 [3, 9]。[3, 9] 与 [8, 10] 重叠，因此更新为 [3, 10]。[11, 12] 与当前结果不重叠，因此单独加入结果。示例 2：
输入：
A = [[1, 3], [7, 9]]
B = [[2, 5], [10, 12]]
输出：
[[1, 5], [7, 9], [10, 12]]
解释：
[1, 3] 和 [2, 5] 重叠，合并为 [1, 5]。[7, 9] 与 [1, 5] 不重叠，因此加入结果。[10, 12] 与 [7, 9] 不重叠，因此继续作为独立区间加入结果。示例 3：
输入：
A = []
B = [[1, 2], [4, 6]]
输出：
[[1, 2], [4, 6]]
解释：
B 相同。start 排序，因此不需要将所有区间重新放到一个数组中排序。i 和 j 分别指向 A 和 B 当前尚未处理的区间。result 中最后一个区间重叠，则直接合并；否则添加一个新区间。start 大于 result[-1][1]，说明两个区间不重叠。start 小于等于 result[-1][1]，说明两个区间存在重叠，可以将结束位置更新为两个区间结束位置的最大值。i 和 j。A 和 B 都还有未处理区间时，比较 A[i][0] 和 B[j][0]。result 最后一个区间重叠。result[-1][1]。result。[1, 3] 和 [3, 5]，如果题目将端点相接视为重叠，则应合并为 [1, 5]。K 个有序区间列表，可以使用最小堆进行 K-way merge，时间复杂度为 O(N log K)。m 和 n 分别为两个输入列表的区间数量。k 为最终合并后的区间数量，最坏情况下为 O(m+n)。class Solution:
def intervalUnion(self, A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
# i 和 j 分别指向两个已经排序的区间列表中的当前位置。
i = 0
j = 0
# result 保存最终的无重叠区间。
# 每处理一个新区间，都只需要检查 result 的最后一个区间。
result = []
# 当两个列表都还有未处理区间时，
# 每次选择起点更小的区间，就能保证整体处理顺序仍然有序。
while i < len(A) and j < len(B):
# 比较两个当前区间的起点。
# 起点更小的区间一定应该先进入合并流程。
if A[i][0] <= B[j][0]:
current = A[i]
# A 中的区间已经被取出，因此将 i 向后移动。
i += 1
else:
current = B[j]
# B 中的区间已经被取出，因此将 j 向后移动。
j += 1
# 如果 result 为空，当前区间直接成为第一个结果区间。
if not result:
result.append([current[0], current[1]])
continue
# 取出结果中的最后一个区间。
# 因为前面的区间已经完成合并，所以只需要比较最后一个。
last = result[-1]
# 如果当前区间的起点小于等于最后一个区间的终点，
# 两个区间重叠或者刚好连接，需要合并。
if current[0] <= last[1]:
# 起点不需要改变，因为 last 已经具有更早的起点。
# 终点取两个区间终点的最大值，保证整个覆盖范围不丢失。
last[1] = max(last[1], current[1])
else:
# 当前区间与之前结果完全分离，
# 因此可以作为一个新的独立区间加入结果。
result.append([current[0], current[1]])
# 当 A 已经处理完之后，B 中剩余的区间仍然保持有序，
# 继续逐个加入相同的合并流程。
while i < len(A):
current = A[i]
i += 1
# 如果结果为空，直接加入当前区间。
if not result:
result.append([current[0], current[1]])
continue
# 只需要检查当前区间与结果最后一个区间的关系。
last = result[-1]
if current[0] <= last[1]:
# 存在重叠，扩展最后一个区间的右边界。
last[1] = max(last[1], current[1])
else:
# 不重叠，创建新的结果区间。
result.append([current[0], current[1]])
# 同理，处理 B 中尚未处理的剩余区间。
while j < len(B):
current = B[j]
j += 1
# 如果结果为空，当前区间直接成为结果。
if not result:
result.append([current[0], current[1]])
continue
# 检查当前区间是否与最后一个结果区间重叠。
last = result[-1]
if current[0] <= last[1]:
# 重叠时只需要更新终点。
last[1] = max(last[1], current[1])
else:
# 不重叠时作为新的独立区间保存。
result.append([current[0], current[1]])
# result 已经按照区间起点排序，并且不存在可以继续合并的相邻区间。
return result掌握同类考点的变体套路与最优解模板，举一反三快速拿下技术面试：