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

您想使用区间树。

Answer 2

创建边界记录列表，其中每个边界的形式为

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

并为每个线段添加两个这样的记录到列表中（每端 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 结束，您将不得不做一些整理。