闭合区间的并集RR

计算科学 算法 数据结构
2021-11-26 23:38:53

上有多个区间,例如,它们的并集应该是是否有用于计算这种联合的特定数据结构(或算法)?R[0,0.5][0.4,1][1.5,2][0,1][1.5,2]

这个问题的一个变体是联合循环域上的区间,例如,从的角度。现在, 呈现不同的角度区间。ππ[π/2,π/2][π/2,π/2]

我编写了一个蛮力算法,但是,我想知道已经存在这方面的研究。

1个回答

如果您按起点对间隔进行排序(可能很复杂O(NlogN)),然后您可以测试相邻区间是否重叠并根据需要合并它们O(N)操作。你最终得到的是不相交的间隔列表。

在周期性域中做到这一点只是稍微困难一些 - 与上述相同,并在操作结束时查看是否可以合并第一个和最后一个合并间隔。