计算段总长度的算法

Question

我正在调查这个问题：

假设我们在 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。

问题

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

Answer 1

您可以进行如下操作：

提取每对的两个坐标并标记它们是否结束一个段（标志）或不（当它们开始一个时）。对这些新对 (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

计算段总长度的算法

Algorithm to total the combined length of segments

algorithm

computer-science

distance

例子

问题