algorithm - 多くの線分の和集合の長さを見つける

Question

開始と終了のx座標の形式で、x軸に太字の線分がいくつかあります。一部の線分が重なっている可能性があります。すべての線分の和集合の長さを見つける方法。

たとえば、線分は5,0から8,0で、その他は9,0から12.0です。両方とも重複していないため、長さの合計は3 + 3=6です。

線分は5,0から8,0で、その他は7,0から12.0です。ただし、範囲が7,0から8,0の場合は重複しています。したがって、長さの和集合は7です。

ただし、x座標は浮動小数点である可能性があります。

Answer 1

線分を2つのEndPointオブジェクトとして表します。各EndPointオブジェクトの形式は<coordinate, isStartEndPoint>です。EndPointすべての線分のすべてのオブジェクトをリストにまとめますendPointList。

アルゴリズム：

• 最初に座標で昇順で並べ替えてendPointListから、開始端点を終了端点の前に配置します（どのセグメントでも、問題ではないため、すべて同じ座標に配置します）。

• この擬似コードに従ってソートされたリストをループします。

  prevCoordinate = -Inf
  numSegment = 0
  unionLength = 0
  
  for (endPoint in endPointList):
      if (numSegment > 0):
          unionLength += endPoint.coordinate - prevCoordinate
  
      prevCoordinate = endPoint.coordinate
  
      if (endPoint.isStartCoordinate):
          numSegment = numSegment + 1
      else:
          numSegment = numSegment - 1
  

変数はnumSegment、セグメント内にいるかどうかを示します。0より大きい場合、セグメント内にあるため、前の終点までの距離を含めることができます。0の場合、現在の終点の前の部分にセグメントが含まれていないことを意味します。

比較ベースのソートアルゴリズムにはOmega（n log n）の下限があり、ループは明らかにO（n）であるため、複雑さはソート部分によって支配されます。したがって、O（n log n）比較ベースのソートアルゴリズムを選択した場合、アルゴリズムの複雑さはO（n log n）と言えます。

Answer 2

レンジツリーを使用。範囲ツリーは、並べ替えられた開始点/終了点と同じように n log(n) ですが、範囲が重複すると要素の数が減るという追加の利点があります (ただし、挿入のコストが増加する可能性があります)。

struct segment {
        struct segment *ll, *rr;
        float lo, hi;
        };

struct segment * newsegment(float lo, float hi) {
struct segment * ret;
ret = malloc (sizeof *ret);
ret->lo = lo; ret->hi = hi;
ret->ll= ret->rr = NULL;
return ret;
}

struct segment * insert_range(struct segment *root, float lo, float hi)
{
if (!root) return newsegment(lo, hi);

        /* non-overlapping(or touching)  ranges can be put into the {l,r} subtrees} */
if (hi < root->lo) {
        root->ll = insert_range(root->ll, lo, hi);
        return root;
        }
if (lo > root->hi) {
        root->rr = insert_range(root->rr, lo, hi);
        return root;
        }

        /* when we get here, we must have overlap; we can extend the current node
        ** we also need to check if the broader range overlaps the child nodes
        */
if (lo < root->lo ) {
        root->lo = lo;
        while (root->ll && root->ll->hi >= root->lo) {
                struct segment *tmp;
                tmp = root->ll;
                root->lo = tmp->lo;
                root->ll = tmp->ll;
                tmp->ll = NULL;
                // freetree(tmp);
                }
        }
if (hi > root->hi ) {
        root->hi = hi;
        while (root->rr && root->rr->lo <= root->hi) {
                struct segment *tmp;
                tmp = root->rr;
                root->hi = tmp->hi;
                root->rr = tmp->rr;
                tmp->rr = NULL;
                // freetree(tmp);
                }
        }

return root;
}

float total_width(struct segment *ptr)
{
float ret;
if (!ptr) return 0.0;

ret = ptr->hi - ptr->lo;
ret += total_width(ptr->ll);
ret += total_width(ptr->rr);

return ret;
}

Answer 3

これは私が Haskell で書いたばかりのソリューションで、以下はインタープリター コマンド プロンプトで実装する方法の例です。セグメントは、タプル [(a,a)] のリストの形式で提示する必要があります。コードからアルゴリズムを理解していただければ幸いです。

import Data.List

unionSegments segments = 
  let (x:xs) = sort segments
      one_segment = snd x - fst x
  in if xs /= []
        then if snd x > fst (head xs) 
                then one_segment - (snd x - fst (head xs)) + unionSegments xs
                else one_segment + unionSegments xs
        else one_segment

*Main> :load "unionSegments.hs"
[1 of 1] Main のコンパイル ( unionSegments.hs、解釈済み ) わかりまし
た。ロードされたモジュール: Main。
*Main> unionSegments [(5,8), (7,12)]
7