union - 区間の和集合

Question

間隔を表すクラスがあります。このクラスには、同等のタイプの 2 つのプロパティ「start」と「end」があります。現在、このような間隔の集合を結合する効率的なアルゴリズムを探しています。

前もって感謝します。

Answer 1

それらを用語の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) です。次に、並べ替えられたアイテムに沿って 1 回のパスでループし、間隔 O(n) を計算します。

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

Answer 3

geocar によるアルゴリズムは、次の場合に失敗します。

s=[tp(0,1),tp(0,3)]

よくわかりませんが、これが正しい方法だと思います：

class tp():
    def __repr__(self):
        return '(%.2f,%.2f)' % (self.start, self.end)
    def __init__(self,start,end): 
        self.start=start
        self.end=end
s=[tp(0,1),tp(0,3),tp(4,5)]
s.sort(key=lambda self: self.start)
print s
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
    if x.end > y[-1].end:
        y[-1].end = x.end
print y

減算のためにも実装しました：

#subtraction
z=tp(1.5,5) #interval to be subtracted
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)]

s.sort(key=lambda self: self.start)
print s
for x in s[:]:
    if z.end < x.start:
        break
    elif z.start < x.start and z.end > x.start and z.end < x.end:
        x.start=z.end
    elif z.start < x.start and z.end > x.end:
        s.remove(x)
    elif z.start > x.start and z.end < x.end:
        s.append(tp(x.start,z.start))
        s.append(tp(z.end,x.end))
        s.remove(x)
    elif z.start > x.start and z.start < x.end and z.end > x.end:
        x.end=z.start
    elif z.start > x.end:
        continue

print s

Answer 4

すべてのポイントを並べ替えます。次に、リストを調べて、「開始」ポイントのカウンターをインクリメントし、「終了」ポイントのカウンターをデクリメントします。カウンターが0に達した場合、それは実際にはユニオンの間隔の1つのエンドポイントです。

カウンターが負になることはなく、リストの最後で0になります。