比如我可能有如下的区间(两端是闭合的而不是开放的)
我想找到只被其中一个覆盖的区间。
在这个例子中,边界如下(
<
表示左边界,>
表示右边界。
(<24.38, <32.16, 38.9999>, <44.35, 50.99>, 53.52>)
有五个基本区间,[24.38, 32.16], [32.16, 38.9999], [38.9999, 44.35], [44.35, 50.99], [50.99, 53.52]。
覆盖五个基本区间的原始区间如下(0表示不覆盖,1表示覆盖)
- [44.35, 53.52]: 0 0 0 1 1
- [44.35, 50.99]: 0 0 0 1 0
- [32.16, 50.99]: 0 1 1 1 0
- [32.16, 38.9999]: 0 1 0 0 0
- [24.38, 38.9999]: 1 1 1 0 0
所以总和是
- sum: 1 3 2 3 1
因此,区间 (24.38, 32.16) 和 (50.99, 53.52) 被原始区间覆盖一次。
请注意,在我的输入示例中,连续的间隔总是共享一端。共享端总是左右交替。我确信没有这个假设会使算法变得更简单或更简单。但如果是这样,就应该使用这个假设。
解决这个问题最有效的算法是什么?算法应该是在线的,也就是说,当一个新的区间进来时,结果只会被有效地更新,而不是从头开始计算。