泸州网站建设价格,韩国搜索引擎排名,建模教程,网站更换主机需要怎么做题目
以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间#xff0c;并返回 一个不重叠的区间数组#xff0c;该数组需恰好覆盖输入中的所有区间 。
示例 1#xff1a; 输入#xff1a;intervals …题目
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1 输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2 输入intervals [[1,4],[4,5]] 输出[[1,5]] 解释区间 [1,4] 和 [4,5] 可被视为重叠区间。
答案
这个问题可以通过使用并查集Disjoint Set Union数据结构来解决。并查集可以高效地合并和查找不相交的集合这正是我们在这个问题中需要的。
下面是一个 Python 实现的解决方案
def merge(intervals):# 定义一个并查集类class UnionFind:def __init__(self, n):self.parent list(range(n))self.rank [0]*ndef find(self, x):if self.parent[x] ! x:self.parent[x] self.find(self.parent[x])return self.parent[x]def union(self, x, y):root_x self.find(x)root_y self.find(y)if root_x ! root_y:if self.rank[root_x] self.rank[root_y]:self.parent[root_y] root_xelse:self.parent[root_x] root_yif self.rank[root_x] self.rank[root_y]:self.rank[root_y] 1# 初始化并查集n len(intervals)uf UnionFind(n)# 按照区间的结束点进行排序intervals.sort(keylambda x: x[1])# 遍历区间列表合并重叠的区间merged []end 0 # 当前合并区间的结束点for start in range(len(intervals)):if start 0 and intervals[start][0] end: # 与前一个区间有重叠merged[-1][1] max(merged[-1][1], intervals[start][1]) # 更新前一个合并区间的结束点else: # 与前一个区间无重叠新建一个合并区间merged.append([intervals[start][0], intervals[start][1]])end intervals[start][1] # 更新当前合并区间的结束点merged[-1][1] end # 处理最后一个合并区间保证其结束点为最后一个区间的结束点return merged代码的执行过程如下
首先创建一个并查集对象用来存储每个区间的父节点和每个集合的秩树的高度。秩被用来在合并两个集合时确定哪棵树应该成为新的根节点。然后将区间按照结束点进行排序这样可以保证在处理每个区间时所有与它重叠的区间都已经处理过。这是因为我们希望合并重叠的区间而不是将它们分开。遍历排序后的区间列表。对于每个区间如果它与前一个区间有重叠即它的开始点等于前一个区间的结束点则更新前一个合并区间的结束点为这两个区间的最大结束点。否则新建一个合并区间并将当前区间的开始点和结束点作为新合并区间的开始点和结束点。在每次新建或更新合并区间后更新当前合并区间的结束点。最后处理完最后一个合并区间后再次更新其结束点以保证其结束点与最后一个区间的结束点相同。
