线段合并长度总和的算法 [英] Algorithm to total the combined length of segments

问题描述

我正在调查此问题：

假设我们在X轴上有N个起点和终点不同的线段。下面的数据结构描述了这一点：

[(start1, end1),..., (startN, endN)]

现在我们要计算这些段的总大小，但重叠不应重复计算。

示例

输入：[(0,3),(1,2), (6,7)]
输出：4

由于线段(1，2)与线段(0，3)重叠，0到3的距离仅为3，6到7的距离为1，因此3+1=4。

问题

是否有针对大输入大小进行此计算的算法？

推荐答案

您可以按如下方式操作：

提取每对的坐标并标记它们是否结束段(标志)或不结束(当它们开始一个段时)。对这些新的对(x，end)进行排序。然后对它们进行处理。当坐标开始分段时，将坐标推入堆栈。当它结束一段时，从堆栈中弹出相应的开始坐标。如果堆栈为空，则将结束坐标和开始坐标之间的差加到总计中：

lst = [(0,3),(1,2), (6,7)]

stack = []
total = 0
for x, end in sorted((x, i) for pair in lst for i, x in enumerate(pair)):
    if end:
        start = stack.pop()
        if not len(stack):
            total += x - start
    else:
        stack.append(x)

print(total)  # 4

这篇关于线段合并长度总和的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！