algorithm - 線分の数直線上の隣接点のリスト?

Question

1から100までの数直線があります。

その数直線の範囲内で、多くの線分を追加および削除できます。これらの線分は、互いに交差したり重なり合ったりすることがあります。

与えられた x1 と x2 に対して、隣接するすべてのポイントのペア (x1 と x2 を含む) を反復処理して、隣接するポイント間を走るすべての線分のリストにアクセスできる効率的なアルゴリズムが必要です。

この黒の数直線と色付きの線分から得られる結果は、次のようになります。

[0-20] -> []
[20-30] -> [red]
[30-40] -> [red, green]
[40-50] -> [green]
[50-60] -> []
[60-80] -> [purple]
[80-100] -> []

Answer 1

You want to use an interval tree.

Answer 2

各境界がフォームである境界レコードのリストを作成します

bound.type = start,finish
bound.position = 0..n
bound.color = red,green,blue...

そして、線分ごとに、そのようなレコードを 2 つリストに追加します (両端に ine)。次に、すべてのレコードを位置で並べ替えます。次のようにリストを反復すると、次のようになります。

colors=[]
write '[0'
for each bound in list
  write '-',bound.pos,'] -> [',colours,']'
  if bound.type = start then 
    add bound.color to colors
  else
    remove bound.type from colors
  write '[',bound.pos
write '-',n'] -> []'

最初の線分が 0 で始まる場合、または最後の線分が n で終わる場合は、少し整理する必要があります。