algorithm - 数直線上の線分の結合を見つける

Question

0 から 1000 までの数直線があります。数直線上に多くの線分があります。すべての線分の x1 は >= 0 で、すべての x2 は < 1000 です。すべての x1 と x2 は整数です。

線分の和集合をすべて見つける必要があります。

この画像では、線分は青で、結合は赤で示されています。

このタイプの問題に対する既存のアルゴリズムはありますか?

Answer 1

marzullo のアルゴリズムを使用できます (詳細については、ウィキペディアを参照してください)。これが私が書いた Python 実装です。

def ip_ranges_grouping(range_lst):
    ##  Based on Marzullo's algorithm
    ##  Input: list of IP ranges
    ##  Returns a new merged list of IP ranges
    table = []
    for rng in range_lst:
        start,end = rng.split('-')
        table.append((ip2int(start),1))
        table.append((ip2int(end),-1))
    table.sort(key=lambda x: x[0])
    for i in range(len(table) - 1):
        if((table[i][0] == table[i+1][0]) and ((table[i][1] == -1) and (table[i+1][1] == 1))):
           table[i],table[i+1] = table[i+1],table[i]

    merged = []
    end = count = 0
    while (end < len(table)):
        start = end
        count += table[end][1]
        while(count > 0): # upon last index, count == 0 and loop terminates
            end += 1
            count += table[end][1]
        merged.append(int2ip(table[start][0]) + '-' + int2ip(table[end][0]))
        end += 1
    return merged

Answer 2

セグメントが動的に変更されない場合、それは単純な問題です。すべてのセグメントを左端で並べ替え、並べ替えられた要素をスキャンするだけです。

struct Seg {int L,R;};

int cmp(Seg a, Seg b) {return a.L < b.L;}

int union_segs(int n, Seg *segs, Segs *output) {
  sort(segs, segs + n, cmp);
  int right_most = -1;
  int cnt = 0;
  for (int i = 0 ; i < n ; i++) {
    if (segs[i].L > right_most) {
      right_most = segs[i].R;
      ++cnt;
      output[cnt].L = segs[i].L;
      output[cnt].R = segs[i].R;
    }
    if (segs[i].R > right_most) {
      right_most = segs[i].R;
      output[cnt].R = segs[i].R;
    }
  }
  return cnt+1;
}

時間計算量は O(nlogn) (ソート) + O(n) (スキャン) です。

セグメントが動的に挿入および削除され、いつでもユニオンを照会したい場合は、range treeなどのより複雑なデータ構造が必要になります。

Answer 3

セグメントの座標が制限された ([0, 1000]) 整数であることを考慮すると、ゼロで初期化されたサイズ 1000 の配列を使用できます。次に、セグメントのセットを実行し、セグメントがカバーする配列のすべてのセルに 1 を設定します。その後、配列を実行して、連続する 1 のシーケンスをチェックするだけです。

---      -----
  ---  ---
1111100111111100

複雑さは、セグメントの数だけでなく、セグメントの長さにも依存します。

これは、浮動小数点セグメントでも機能する別の方法です。セグメントを並べ替えます。次に、並べ替えられたセグメントを移動し、隣接する各セグメントの境界を比較するだけです。それらが交差する場合、それらは同じ組合にあります。