algorithm - 在一组间隔中查找间隔模式

Question

假设我注册了一组“开启”间隔 [tstart, tend]

a = [[0+t, 3.9+t], [7.1+t, 8.0+t], [9.02+t, 10.2+t]]

如何为该模式找到最佳匹配偏移量 t 以匹配另一组间隔:

b = [[5, 6], [7, 10], [11, 15], [18, 19], [20, 21] ... ]

[ t  ]

      ----   - -

- --- ----   - - --- -- ----    - --

Answer 1

普通算法(不一定是最有效的):选择偏移量 t 的所有值，这些值会导致每个集合中的一个间隔在其起点或终点对齐。对于这些偏移值中的每一个，计算总重叠以找到最大值。复杂度为 O(n^3)，其中 n 是集合的大小(a 和 b 的最大值)。给定偏移的重叠计算是 O(n)，可能的偏移值的数量是 O(n^2)。

在您的示例中，偏移量为:
将区间 a[0] 的开始与 b 中所有区间的开始相匹配:

5-0=5, 7-0=7, 11=0=11, ....

将区间 a[0] 的结尾匹配到 b 中所有区间的结尾:

6-3.9=2.1, 10-3.9=6.1, 15-3.9=11.1,....

我们继续对 a 中的所有间隔执行相同的操作，并收集所有产生的偏移值。然后我们计算每个偏移量的重叠。