Interval intersection to find interval covered once

问题描述 投票:0回答:0

比如我可能有如下的区间(两端是闭合的而不是开放的)

  • [44.35, 53.52]
  • [44.35, 50.99]
  • [32.16, 50.99]
  • [32.16, 38.9999]
  • [24.38, 38.9999]

我想找到只被其中一个覆盖的区间。

在这个例子中,边界如下(

<
表示左边界,
>
表示右边界。

(<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) 被原始区间覆盖一次。

请注意,在我的输入示例中,连续的间隔总是共享一端。共享端总是左右交替。我确信没有这个假设会使算法变得更简单或更简单。但如果是这样,就应该使用这个假设。

解决这个问题最有效的算法是什么?算法应该是在线的,也就是说,当一个新的区间进来时,结果只会被有效地更新,而不是从头开始计算。

algorithm search data-structures big-o interval-intersection
© www.soinside.com 2019 - 2024. All rights reserved.