•  06-07-2019
  •  | 
  •  

質問

間隔を表すクラスがあります。このクラスには2つのプロパティ＆quot; start＆quot;があります。および「終了」比較可能なタイプの。現在、このような一連の間隔を結合する効率的なアルゴリズムを探しています。

事前に感謝します。

役に立ちましたか？

解決

用語のいずれか（たとえば、開始）で並べ替えてから、リスト内を移動するときに、その（右側の）隣との重複を確認します。

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

他のヒント

スイープラインアルゴリズムを使用します。基本的に、リスト内のすべての値をソートします（各アイテムとともに間隔の開始または終了のいずれかを保持します）。この操作はO（n log n）です。次に、ソートされたアイテムに沿って単一パスでループし、間隔O（n）を計算します。

O（n log n）+ O（n）= O（n log n）

この問題は何度も解決されていることがわかりました-さまざまなレベルの空想で、命名法の下で： http://en.wikipedia.org/wiki/Interval_tree 、 http： //en.wikipedia.org/wiki/Segment_tree 、および「RangeTree」

（OPの質問には、これらのデータ構造が重要な間隔の大きなカウントが関係するため）

Pythonライブラリー選択の私自身の選択に関して：

  • テストから、フル機能とpython current（非ビットローテート）の点で最も釘付けになっているものが見つかりました：SymPyの 'Interval'および 'Union'クラス、参照： http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

  • 別の見栄えの良い選択肢、パフォーマンスは高いが機能が豊富でないオプション（例：浮動小数点範囲の削除では機能しませんでした）： https://pypi.python.org/pypi/Banyan

最後に：IntervalTree、SegmentTree、RangeTreeのいずれかの下でSO自体を検索すると、さらに多くの回答/フックが見つかります

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

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

カウンターは決して負にならず、リストの最後で0になります。

C ++で区間の和集合の合計を見つける

#include <iostream>
#include <algorithm>

struct interval
{
    int m_start;
    int m_end;
};

int main()
{
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } };

    std::sort(
        arr,
        arr + sizeof(arr) / sizeof(interval),
        [](const auto& i, const auto& j) { return i.m_start < j.m_start; });

    int total = 0;
    auto current = arr[0];
    for (const auto& i : arr)
    {
        if (i.m_start >= current.m_end)
        {
            total += current.m_end - current.m_start;
            current = i;
        }
        else if (i.m_end > current.m_end)
        {
            current.m_end = i.m_end;
        }
    }

    total += current.m_end - current.m_start;
    std::cout << total << std::endl;
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top