间隔的并集 [英] Union of intervals

问题描述

我有一个代表间隔的班级.此类具有可比较类型的两个属性开始"和结束".现在，我正在寻找一种有效的算法来合并一组这样的间隔.

I've got a class representing an interval. This class has two properties "start" and "end" of a comparable type. Now I'm searching for an efficient algorithm to take the union of a set of such intervals.

先谢谢了.

推荐答案

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

Sort them by one of the terms (start, for example), then check for overlaps with its (right-hand) neighbor as you move through the list.

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

这篇关于间隔的并集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！