间隔联盟

Question

我有一个代表间隔的班级.该类具有可比类型的两个属性"start"和"end".现在我正在寻找一种有效的算法来结合一组这样的区间.

提前致谢.

Answer 1

按其中一个术语(例如,开始)对它们进行排序,然后在列表中移动时检查与其(右侧)邻居的重叠.

class tp():
    def __repr__(self):
        return '(%d,%d)' % (self.start, self.end)
    def __init__(self,start,end): 
        self.start=start
        self.end=end
s=[tp(5,10),tp(7,8),tp(0,5)]
s.sort(key=lambda self: self.start)
y=[ s[0] ]
for x in s[1:]:
  if y[-1].end < x.start:
      y.append(x)
  elif y[-1].end == x.start:
      y[-1].end = x.end

Answer 2

使用扫描线算法。基本上，您对列表中的所有值进行排序（同时保持每个项目是间隔的开始还是结束）。这个操作是 O(n log n)。然后沿着排序的项目单次循环并计算间隔 O(n)。

O(n log n) + O(n) = O(n log n)

Answer 3

事实证明，这个问题已经解决了很多次——在不同程度的幻想中，在命名法下：http : //en.wikipedia.org/wiki/Interval_tree，http : //en.wikipedia.org /wiki/Segment_tree ，还有“RangeTree”

（因为 OP 的问题涉及大量间隔，这些数据结构很重要）

就我自己选择的python库选择而言：

• 从测试中，我发现在功能齐全和 Python 当前（非位腐烂）方面最重要的是：来自 SymPy 的“Interval”和“Union”类，请参阅： http://sympystats.wordpress。 com/2012/03/30/simplifying-sets/

• 另一个好看的选择，一个更高的性能但更少的功能丰富的选项（例如，不能去除浮点范围）：https : //pypi.python.org/pypi/Banyan

最后：搜索 SO 本身，在 IntervalTree、SegmentTree、RangeTree 中的任何一个下，你会找到更多的答案/钩子