给定一组闭合区域[a,b]
,其中a
和b
是整数,我需要找到另一组覆盖相同数字但不相交的区域
我认为可以通过多次迭代集来简单地完成,但我正在寻找一个好的算法推荐。请帮助。
编辑:为了澄清,得到的区域不能大于原来的区域,我不得不提出由原来的区域包含的不相交区域。换句话说,我需要在它们重叠的边界上分割原始区域。
的例子:
3,8
1,4
7,9
11,14
结果:1,3
3,4
4,7
7,8
8,9
11,14
将所有端点从左到右排序(记住它们的类型:start或end)。从左向右滑动。保持一个从0开始的计数器。当你遇到start:时,增加计数器。当您遇到end:减量(注意计数器总是至少为0)。
记住最后两点。如果计数器大于零-并且最后两个点不同(防止空范围)-添加最后两个点之间的间隔。
伪代码:
points = all interval endpoints
sort(points)
previous = points[0]
counter = 1
for(int i = 1; i < #points; i++) {
current = points[i]
if (current was start point)
counter++
else
counter--
if (counter > 0 and previous != current)
add (previous, current) to output
previous = current
}
(这是我今天早些时候发布的一个答案的修改,我发现它有一个逻辑错误后删除了。后来我意识到我可以修改Vincent van der Weele使用括号深度的优雅想法来修复错误)
On Edit:修改为能够接受长度为0的间隔
称长度为0 的区间[a,a]为本质,如果a不作为任何长度> 0的区间的端点出现。例如,在[1,3],[2,2],[3,3],[4,4]中,0长度的间隔[2,2]和[4,4]是必要的,但[3,3]不是。不必要的0长度间隔是多余的,因此不需要出现在最终输出中。当初始扫描间隔列表(加载基本数据结构)时,记录长度为0的间隔对应的点,以及长度> 0的间隔端点。扫描完成后,将基本 0长度间隔对应的每个点的两个实例添加到端点列表中,然后对端点列表进行排序。得到的数据结构是一个多集,其中唯一的重复对应于基本的0长度间隔。
对于区间内的每个端点,定义端点的pdelta(括号delta)为该点作为左端点出现的次数减去它作为右端点出现的次数。将它们存储在由端点键控的字典中。
[a,b]其中a,b是端点列表的前两个元素,是不相交区间列表中的第一个区间。定义b的圆括号深度为p [a]和p [b]的和。我们循环遍历其余端点,如下所示:
在每次通过循环时查看b的括号深度。如果它不为0,则b仍然需要再进行一次间隔。设a = b,新的p是列表中的下一个值。将括号深度调整为新b的pdelta,并将[a,b]添加到不相交间隔列表中。否则(如果b的括号深度为0)让下一个[a,b]是列表中下一个两个点,并相应地调整括号深度。
下面是一个Python实现:
def disjointify(intervals):
if len(intervals) == 0: return []
pdelta = {}
ends = set()
disjoints = []
onePoints = set() #onePoint intervals
for (a,b) in intervals:
if a == b:
onePoints.add(a)
if not a in pdelta: pdelta[a] = 0
else:
ends.add(a)
ends.add(b)
pdelta[a] = pdelta.setdefault(a,0) + 1
pdelta[b] = pdelta.setdefault(b,0) - 1
onePoints.difference_update(ends)
ends = list(ends)
for a in onePoints:
ends.extend([a,a])
ends.sort()
a = ends[0]
b = ends[1]
pdepth = pdelta[a] + pdelta[b]
i = 1
disjoints.append((a,b))
while i < len(ends) - 1:
if pdepth != 0:
a = b
b = ends[i+1]
pdepth += pdelta[b]
i += 1
else:
a = ends[i+1]
b = ends[i+2]
pdepth += (pdelta[a] + pdelta[b])
i += 2
disjoints.append((a,b))
return disjoints
说明各种边缘情况的示例输出:
>>> example = [(1,1), (1,4), (2,2), (4,4),(5,5), (6,8), (7,9), (10,10)]
>>> disjointify(example)
[(1, 2), (2, 2), (2, 4), (5, 5), (6, 7), (7, 8), (8, 9), (10, 10)]
>>> disjointify([(1,1), (2,2)])
[(1, 1), (2, 2)]
(我使用Python元组来表示封闭区间,尽管它有一个小缺点,看起来像开放区间的标准数学符号)。
最后一点:将结果称为不相交区间的集合可能不准确,因为其中一些区间具有非空的(尽管是1点相交)