将重叠区域分割成不相交的区域

Question

给定一组封闭区域 [a,b]，其中 a 和 b 是整数，我需要找到另一组覆盖相同数字但不相交的区域。

我想可以通过多次遍历集合来天真地做到这一点，但我正在为此寻找一个好的算法的推荐。请帮忙。

编辑：

澄清一下，生成的区域不能大于原始区域，我必须想出原始区域包含的不相交区域。换句话说，我需要在它们重叠的边界上分割原始区域。

示例：

3,8
1,4
7,9
11,14

结果：

1,3
3,4
4,7
7,8
8,9
11,14

Answer 1

只需将所有端点从左到右排序（记住它们的类型：开始或结束）。从左向右轻扫。保持计数器从 0 开始。每当遇到开始时：增加计数器。当你遇到结束时：递减（注意计数器总是至少为 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
}

Answer 2

（这是对我今天早些时候发布的一个答案的修改，在我发现它有逻辑错误后我删除了它。后来我意识到我可以修改 Vincent van der Weele 使用括号深度修复的优雅想法错误）

编辑时：修改为能够接受长度为 0 的区间

调用长度为 0 的区间 [a,a] 必要的 如果 a 没有同时出现为任何长度 > 0 的区间的端点。例如，在 [ 1,3]、[2,2]、[3,3]、[4,4] 0 长度区间 [2,2] 和 [4,4] 是必不可少的，但 [3,3] 不是。不重要的 0 长度间隔是多余的，因此不需要出现在最终输出中。当初始扫描间隔列表（加载基本数据结构）时，记录对应于 0 长度间隔的点，以及长度 > 0 的间隔的端点。扫描完成后，每个点的两个实例对应于 essential 0 长度间隔被添加到端点列表中，然后进行排序。生成的数据结构是一个多重集，其中唯一的重复对应于基本的 0 长度间隔。

对于区间中的每个端点，将端点的 pdelta（括号增量）定义为该点作为左端点出现的次数减去它出现的次数作为正确的端点。将这些存储在由端点键入的字典中。

[a,b] 其中 a,b 是端点列表的前两个元素，是不相交区间列表中的第一个区间。将 b 的括号深度定义为 pdelta[a] 和 pdelta[b] 的总和。我们按如下方式遍历其余端点：

在每次循环中查看 b 的括号深度。如果它不为 0，那么 b 仍然需要一个间隔。让 a = b 并让新的 p 成为列表中的下一个值。将括号深度调整为新 b 的 pdelta，并将 [a,b] 添加到不相交间隔列表中。否则（如果 b 的括号深度为 0）让下一个 [a,b] 成为列表中的下一个 two 点并相应地调整括号深度。

这是一个 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 点交集

将重叠区域分割成不相交的区域

segment overlapping regions into disjoint regions

algorithm

intervals