重畳区間を結合 – 数値範囲の交差

Merging overlapping intervals the naive way – StackOverflow

最初にソートすればO(n log n),ソート済みならO(n).

def groupby_seq(lst, assume_sorted=False):
    it = iter(lst) if assume_sorted else iter(sorted(lst))
    b, a = next(it)
    for s, e in it:
        if a < s:
            yield (b, a)
            b = s
        a = e
    yield (b, a)


lst = [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]
list(groupby_seq(lst))
[(0, 1), (3, 8), (9, 12)]

 
 
関連:
2つのリスト内の範囲が交差しない範囲集合を求める

 
3つのリストからスパンのセットが重複する値を見つける方法は?

数値範囲の交差に関するアルゴリズム問題,範囲集合をコンパクトに表す方法

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください