（这是我今天早些时候发布的一个答案的修改，我在发现它有一个逻辑错误之后删除了 . 我后来意识到我可以修改Vincent van der Weele使用括号深度修复bug的优雅想法）
在编辑：修改为能够接受长度为0的间隔
如果不是't also appear as an endpoint of any interval of length > 0. For example, in [1,3], [2,2], [3,3], [4,4] the 0-length intervals [2,2] and [4,4] are essential but [3,3] isn' t，则调用长度为0的区间[a，a] . 不必要的0长度间隔是冗余的，因此不需要出现在最终输出中 . 当最初扫描间隔列表（加载基本数据结构）时，记录对应于0长度间隔的点，以及长度> 0的间隔的 endpoints . 当扫描完成时，每个点的两个实例对应于必要0将长度间隔添加到 endpoints 列表中，然后对其进行排序 . 得到的数据结构是多重集，其中唯一的重复对应于基本的0长度间隔 .
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
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
}
2 回答
（这是我今天早些时候发布的一个答案的修改，我在发现它有一个逻辑错误之后删除了 . 我后来意识到我可以修改Vincent van der Weele使用括号深度修复bug的优雅想法）
在编辑：修改为能够接受长度为0的间隔
如果不是't also appear as an endpoint of any interval of length > 0. For example, in [1,3], [2,2], [3,3], [4,4] the 0-length intervals [2,2] and [4,4] are essential but [3,3] isn' t，则调用长度为0的区间[a，a] . 不必要的0长度间隔是冗余的，因此不需要出现在最终输出中 . 当最初扫描间隔列表（加载基本数据结构）时，记录对应于0长度间隔的点，以及长度> 0的间隔的 endpoints . 当扫描完成时，每个点的两个实例对应于必要0将长度间隔添加到 endpoints 列表中，然后对其进行排序 . 得到的数据结构是多重集，其中唯一的重复对应于基本的0长度间隔 .
对于区间中的每个 endpoints ，将 endpoints 的pdelta（括号增量）定义为该点显示为左 endpoints 的次数减去它显示为右 endpoints 的次数 . 将它们存储在由 endpoints 键入的字典中 .
[a，b]其中a，b是 endpoints 列表的前两个元素是不相交间隔列表中的第一个间隔 . 将b的括号深度定义为pdelta [a]和pdelta [b]的总和 . 我们循环遍历其余 endpoints ，如下所示：
在每次通过循环时，请查看b的括号深度 . 如果它不是0，则还需要一个间隔 . 设a = b并让新p成为列表中的下一个值 . 将括号深度调整为新b的pdelta，并将[a，b]添加到不相交的间隔列表中 . 否则（如果b的括号深度为0），让下一个[a，b]成为列表中的下两个点，并相应地调整括号深度 .
这是一个Python实现：
示例输出说明了各种边缘情况：
（我使用Python元组来表示闭合的区间，即使它具有看起来像开放区间的标准数学符号的小缺点） .
最后一句：将结果称为不相交区间的集合可能不准确，因为这些区间中的一些区间虽然有1点交叉点但非空
只需从左到右排序所有 endpoints （记住它们的类型：开始或结束） . 从左到右Swype . 保持计数器从0开始 . 每当你遇到一个开始：增加计数器 . 当你遇到一个结束时：减量（注意计数器总是至少为0） .
跟踪最后两点 . 如果计数器大于零 - 并且最后两个点不同（防止空范围） - 添加最后两个点之间的间隔 .
伪代码：